Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-147 | 2nd October 2016 18:20

Rectangles Are Nonnegative Juntas

RSS-Feed




Revision #1
Authors: Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Accepted on: 2nd October 2016 18:20
Downloads: 1212
Keywords: 


Abstract:

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ g^n$ can be simulated by a \emph{nonnegative combination of juntas}. This is a new formalization for the intuition that each low-communication randomized protocol can only ``query'' few inputs of $f$ as encoded by the gadget $g$. Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of $f$. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy.

As applications, we resolve several open problems from prior work: We show that $\SBPcc$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\MAcc \neq \SBPcc$. These results answer questions of Klauck~({\small CCC 2003}) and B{\"o}hler et al.~({\small JCSS 2006}). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al.~({\small ICALP 2014}) for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the Clique vs.~Independent Set problem.


Paper:

TR14-147 | 6th November 2014 04:51

Rectangles Are Nonnegative Juntas





TR14-147
Authors: Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Publication: 7th November 2014 15:07
Downloads: 3010
Keywords: 


Abstract:

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ g^n$ can be simulated by a \emph{nonnegative combination of juntas}. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only ``query'' few inputs of $f$ as encoded by the gadget $g$. Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided zero-communication models by a corresponding query complexity measure of $f$. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy.

As applications, we resolve several open problems from prior work: We show that $\SBPcc$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\MAcc \neq \SBPcc$. These results answer questions of Klauck~({\small CCC 2003}) and B{\"o}hler et al.~({\small JCSS 2006}). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al.~({\small ICALP 2014}) for partial matrices.



ISSN 1433-8092 | Imprint