ECCC-Report TR19-067https://eccc.weizmann.ac.il/report/2019/067Comments and Revisions published for TR19-067en-usMon, 02 May 2022 18:14:11 +0300
Revision 1
| Sign rank vs Discrepancy |
Hamed Hatami,
Kaave Hosseini,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2019/067#revision1Sign-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)}$.
In connection to learning theory, our result implies the existence of Boolean matrices whose entries are represented by points and half-spaces in dimension $3$, and yet, the normalized margin of any such representation, even in higher dimensions, is bound to be very small.
In the context of communication complexity, 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.
Mon, 02 May 2022 18:14:11 +0300https://eccc.weizmann.ac.il/report/2019/067#revision1
Paper TR19-067
| Sign rank vs Discrepancy |
Hamed Hatami,
Kaave Hosseini,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2019/067Sign-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.
Tue, 07 May 2019 12:52:08 +0300https://eccc.weizmann.ac.il/report/2019/067