On randomized one-round communication complexity
Ilan Kremer, Noam Nisan, Dana Ron · 1995
We present several results regarding randomized oneround communication complexity. These 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. 1 Introduction In this paper we are concerned with randomized twoparty communication complexity as defined by Yao [21]: Alice holds an input x, Bob holds an input y, and they wish to compute a given function f(x; y), to which end they communicate with each other via a randomized protocol. We allow them bounded, twosided error. We study very simple types of protocols which include only one round of communication. These protocols were introduced by Yao in his original communication complexity paper [21] and were later studied by several authors (cf. [17, 1]). In a one-round protocol, Alice is allowed to send a single message (depending upon her input x and upon her random coin flips) to Bob who must then...