Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-067 | 6th May 2019 19:23

Sign rank vs Discrepancy



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 is only $3$, and yet its discrepancy is $2^{-\Omega(n)}$. We note that every matrix of sign-rank $2$ has discrepancy $n^{-O(1)}$.
Our result in particular implies that there are Boolean functions with $O(1)$ unbounded error randomized communication complexity while having $\Omega(n)$ weakly unbounded error randomized communication complexity.

ISSN 1433-8092 | Imprint