The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.
In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ... more >>>

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.
For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ... more >>>