We prove that the modular communication complexity of the undirected graph connectivity problem UCONN equals Theta(n), in contrast to the well-known Theta(n*log n) bound in the deterministic case, and to the Omega(n*loglog n) lower bound in the nondeterministic case, recently proved by Raz and Spieker. We obtain our result by ... more >>>

We examine the power of Boolean functions with low L_1 norms in several settings. In large part of the recent literature, the degree of a polynomial which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function. However, some functions ... more >>>

The ``log rank'' conjecture consists in the question how exact the deterministic communication complexity of a problem can be determinied in terms of algebraic invarants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. We show that the ... more >>>