ECCC-Report TR22-165https://eccc.weizmann.ac.il/report/2022/165Comments and Revisions published for TR22-165en-usWed, 23 Nov 2022 01:24:49 +0200
Paper TR22-165
| Separation of the factorization norm and randomized communication complexity |
TsunMing Cheung,
Hamed Hatami,
Kaave Hosseini,
Morgan Shirley
https://eccc.weizmann.ac.il/report/2022/165 In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate $\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate $\gamma_2$ norm with the $\gamma_2$ norm holds.
We answer the question of Linial and Shraibman in the negative by exhibiting a $2^n\times2^n $ Boolean matrix with $\gamma_2$ norm $2^{\Omega(n)}$ and randomized communication complexity $O(\log n)$.
As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23).
Our result also implies a conjecture of Sherif (Ph.D. thesis) that the $\gamma_2$ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size. Wed, 23 Nov 2022 01:24:49 +0200https://eccc.weizmann.ac.il/report/2022/165