On randomized one-round communication complexity
We present several results regarding randomized one-round communication complexity. Our results include a connection to the VC-dimension, a study of the problem of computing the inner product of two real valued vectors, and a relation between "simultaneous" protocols and one-round protocols.
communication complexity one-round and simultaneous protocols vc-dimension