Citation
I. Kremer et al., On randomized one-round communication complexity, COMP COMPLE, 8(1), 1999, pp. 21-49
Citations number
25
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL COMPLEXITY
ISSN journal
10163328
→ ACNP
Volume
8
Issue
1
Year of publication
1999
Pages
21 - 49
Database
ISI
SICI code
1016-3328(1999)8:1<21:OROCC>2.0.ZU;2-U
Abstract
We present several results regarding randomized one-round communication com
plexity. Our results include a connection to the VC-dimension, a study of t
he problem of computing the inner product of two real valued vectors, and a
relation between "simultaneous" protocols and one-round protocols.