ECCC-Report TR15-049https://eccc.weizmann.ac.il/report/2015/049Comments and Revisions published for TR15-049en-usTue, 06 Mar 2018 17:58:27 +0200
Revision 1
| The Landscape of Communication Complexity Classes |
Mika Göös,
Toniann Pitassi,
Thomas Watson
https://eccc.weizmann.ac.il/report/2015/049#revision1We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on the state of structural communication complexity.
Among our new results we show that $MA\not\subseteq ZPP^{NP[1]}$, that is, Merlin--Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one $NP$ query. Here the class $ZPP^{NP[1]}$ has the property that generalizing it in the slightest ways would make it contain $AM\cap coAM$, for which it is notoriously open to prove any explicit lower bounds. We also prove that $US\not\subseteq ZPP^{NP[1]}$, where $US$ is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that $US\not\subseteq coDP$, where $DP$ is the class of differences of two $NP$ sets. Finally, we explore an intriguing open issue: are rank-$1$ matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerning $PP$ that sheds light on this issue and strengthens some previously known separations.Tue, 06 Mar 2018 17:58:27 +0200https://eccc.weizmann.ac.il/report/2015/049#revision1
Paper TR15-049
| The Landscape of Communication Complexity Classes |
Mika Göös,
Toniann Pitassi,
Thomas Watson
https://eccc.weizmann.ac.il/report/2015/049We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on the state of structural communication complexity.
Among our new results we show that $MA\not\subseteq ZPP^{NP[1]}$, that is, Merlin--Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one $NP$ query. Here the class $ZPP^{NP[1]}$ has the property that generalizing it in the slightest ways would make it contain $AM\cap coAM$, for which it is notoriously open to prove any explicit lower bounds. We also prove that $US\not\subseteq ZPP^{NP[1]}$, where $US$ is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that $US\not\subseteq coDP$, where $DP$ is the class of differences of two $NP$ sets. Finally, we explore an intriguing open issue: are rank-$1$ matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerning $PP$ that sheds light on this issue and strengthens some previously known separations.Fri, 03 Apr 2015 23:19:40 +0300https://eccc.weizmann.ac.il/report/2015/049