Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Landscape of Communication Complexity Classes

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between \({\mathsf{P}}\) and \({\mathsf{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 \({\mathsf{MA} \not\subseteq \mathsf{ZPP}^{\mathsf{NP}[1]}}\), that is, Merlin–Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one \({\mathsf{NP}}\) query. Here the class \(\mathsf{ZPP}^{\mathsf{NP}[1]}\) has the property that generalizing it in the slightest ways would make it contain \({\mathsf{AM} \cap \mathsf{coAM}}\), for which it is notoriously open to prove any explicit lower bounds. We also prove that \({\mathsf{US} \not\subseteq \mathsf{ZPP}^{\mathsf{NP}[1]}}\), where \({\mathsf{US}}\) is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that \({\mathsf{US} \not\subseteq \mathsf{coDP}}\), where \({\mathsf{DP}}\) is the class of differences of two \({\mathsf{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 \({\mathsf{PP}}\) that sheds light on this issue and strengthens some previously known separations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aaronson, Scott: Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Proceedings of the Royal Society A 461(2063), 3473–3482 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory 1(1).

  • László Babai, Peter Frankl & Janos Simon (1986). Complexity Classes in Communication Complexity Theory. In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), 337–347. IEEE.

  • Ziv Bar-Yossef, T.S., Jayram, Ravi Kumar, Sivakumar, D.: An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences 68(4), 702–732 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Beigel, Richard: Bounded Queries to SAT and the Boolean Hierarchy. Theoretical Computer Science 84(2), 199–223 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  • Andreas Blass & Yuri Gurevich: On the Unique Satisfiability Problem. Information and Control 55(1–3), 80–88 (1982)

    MathSciNet  MATH  Google Scholar 

  • Böhler, Elmar, Glaßer, Christian, Meister, Daniel: Error-Bounded Probabilistic Computations Between MA and AM. Journal of Computer and System Sciences 72(6), 1043–1076 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler & Prashant Vasudevan (2017). On the Power of Statistical Zero Knowledge. In Proceedings of the 58th Symposium on Foundations of Computer Science, 708–719. IEEE.

  • Harry Buhrman, Nikolai Vereshchagin & Ronald de Wolf (2007). On Computation and Communication with Small Bias. In Proceedings of the 22nd Conference on Computational Complexity (CCC), 24–32. IEEE.

  • Cai, Jin-Yi: \({\rm S}_2{\rm P} \subseteq {\rm ZPP}^{\rm NP}\). Journal of Computer and System Sciences 73(1), 25–35 (2007)

    Article  MathSciNet  Google Scholar 

  • Jin-Yi Cai & Venkatesan Chakaravarthy: On Zero Error Algorithms Having Oracle Access to One Query. Journal of Combinatorial Optimization 11(2), 189–202 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Canetti, Ran: More on BPP and the Polynomial-Time Hierarchy. Information Processing Letters 57(5), 237–241 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  • Amit Chakrabarti, Graham Cormode, Navin Goyal & Justin Thaler (2014a). Annotations for Sparse Data Streams. In Proceedings of the 25th Symposium on Discrete Algorithms (SODA), 687–706. ACM-SIAM.

  • Chakrabarti, Amit, Cormode, Graham, McGregor, Andrew, Thaler, Justin: Annotations in Data Streams. ACM Transactions on Algorithms 11(1), 7 (2014b)

    Article  MathSciNet  MATH  Google Scholar 

  • Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler & Suresh Venkatasubramanian (2015). Verifiable Stream Computation and Arthur–Merlin Communication. In Proceedings of the 30th Computational Complexity Conference (CCC), 217–243. Schloss Dagstuhl.

  • Chang, Richard, Kadin, Jim, Rohatgi, Pankaj: On Unique Satisfiability and the Threshold Behavior of Randomized Reductions. Journal of Computer and System Sciences 50(3), 359–373 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Richard Chang & Suresh Purini (2008). Amplifying \({\rm ZPP}^{\rm SAT[1]}\) and the Two Queries Problem. In Proceedings of the 23rd Conference on Computational Complexity (CCC), 41–52. IEEE.

  • Arkadev Chattopadhyay & Nikhil Mande (2017). Weights at the Bottom Matter When the Top is Heavy. Technical Report TR17-083, Electronic Colloquium on Computational Complexity (ECCC). URL http://eccc.weizmann.ac.il/report/2017/083/.

  • Damm, Carsten, Krause, Matthias, Meinel, Christoph, Waack, Stephan: On Relations Between Counting Communication Complexity Classes. Journal of Computer and System Sciences 69(2), 259–280 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière & Jérémie Roland (2016). Relative Discrepancy Does Not Separate Information and Communication Complexity. ACM Transactions on Computation Theory 9(1), 4:1–4:15.

  • Forster, Jürgen: A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. Journal of Computer and System Sciences 65(4), 612–625 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Fortnow, Lance, Impagliazzo, Russell, Kabanets, Valentine, Umans, Christopher: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3), 353–376 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Anat Ganor, Gillat Kol & Ran Raz (2016). Exponential Separation of Information and Communication for Boolean Functions. Journal of the ACM 63(5), 46:1–46:31.

  • Dmitry Gavinsky & Shachar Lovett (2014). En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 514–524. Springer.

  • Dmitry Gavinsky & Alexander Sherstov: A Separation of NP and coNP in Multiparty Communication Complexity. Theory of Computing 6(1), 227–245 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Oded Goldreich & David Zuckerman (2011). Another Proof That \(\rm BPP\it \subseteq \rm PH\it \) (and More). In Studies in Complexity and Cryptography, 40–53. Springer.

  • Shafi Goldwasser & Michael Sipser (1986). Private Coins versus Public Coins in Interactive Proof Systems. In Proceedings of the 18th Symposium on Theory of Computing (STOC), 59–68. ACM.

  • Mika Göös, Pritish Kamath, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for \({\rm P}^{\rm NP}\). In Proceedings of the 32nd Computational Complexity Conference (CCC), 12:1–12:16. Schloss Dagstuhl.

  • Göös, Mika, Lovett, Shachar, Meka, Raghu, Watson, Thomas, Zuckerman, David: Rectangles Are Nonnegative Juntas. SIAM Journal on Computing 45(5), 1835–1869 (2016a)

    Article  MathSciNet  MATH  Google Scholar 

  • Mika Göös, Toniann Pitassi & Thomas Watson (2016b). Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication. Algorithmica 76(3), 684–719. Special issue on information complexity and applications.

  • Mika Göös & Thomas Watson (2016). Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing 12(1), 1–23. Special issue for selected papers from APPROX–RANDOM 2014.

  • Vince Grolmusz & Gábor Tardos: A Note on Non-Deterministic Communication Complexity with Few Witnesses. Theory of Computing Systems 36(4), 387–391 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Tom Gur & Ran Raz: Arthur-Merlin Streaming Complexity. Information and Computation 243, 145–165 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Tom Gur & Ron Rothblum (2015). Non-Interactive Proofs of Proximity. In Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS), 133–142. ACM.

  • Bernd Halstenberg & Rüdiger Reischuk: Relations Between Communication Complexity Classes. Journal of Computer and System Sciences 41(3), 402–429 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  • Han, Yenjo, Hemaspaandra, Lane, Thierauf, Thomas: Threshold Computation and Cryptographic Security. SIAM Journal on Computing 26(1), 59–78 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Russell Impagliazzo & Ryan Williams (2010). Communication Complexity with Synchronized Clocks. In Proceedings of the 25th Conference on Computational Complexity (CCC), 259–269. IEEE.

  • T.S. Jayram, Ravi Kumar & D. Sivakumar (2003). Two Applications of Information Complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), 673–682. ACM.

  • Jukna, Stasys: On Graph Complexity. Combinatorics, Probability, & Computing 15(6), 855–876 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Stasys Jukna (2012). Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer.

  • Volker Kaibel & Stefan Weltge: A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially. Discrete & Computational Geometry 53(2), 397–401 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Karchmer, Mauricio, Newman, Ilan, Saks, Michael, Wigderson, Avi: Non-Deterministic Communication Complexity with Few Witnesses. Journal of Computer and System Sciences 49(2), 247–257 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Hartmut Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. In Proceedings of the 18th Conference on Computational Complexity (CCC), 118–134. IEEE.

  • Klauck, Hartmut: Lower Bounds for Quantum Communication Complexity. SIAM Journal on Computing 37(1), 20–46 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Hartmut Klauck (2010). A Strong Direct Product Theorem for Disjointness. In Proceedings of the 42nd Symposium on Theory of Computing (STOC), 77–86. ACM.

  • Hartmut Klauck (2011). On Arthur Merlin Games in Communication Complexity. In Proceedings of the 26th Conference on Computational Complexity (CCC), 189–199. IEEE.

  • Hartmut Klauck & Ved Prakash (2013). Streaming Computations with a Loquacious Prover. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), 305–320. ACM.

  • Hartmut Klauck & Ved Prakash (2014). An Improved Interactive Streaming Algorithm for the Distinct Elements Problem. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 919–930. Springer.

  • Eyal Kushilevitz & Noam Nisan (1997). Communication Complexity. Cambridge University Press.

  • Tak Wah Lam & Walter Ruzzo: Results on Communication Complexity Classes. Journal of Computer and System Sciences 44(2), 324–342 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  • Jianhua Lin (1991). Divergence Measures Based on the Shannon Entropy. IEEE Transactions on Information Theory 37(1), 145–151. ISSN 0018-9448.

  • Nathan Linial & Adi Shraibman: Learning Complexity vs Communication Complexity. Combinatorics, Probability, & Computing 18(1–2), 227–245 (2009)

    MathSciNet  MATH  Google Scholar 

  • Lokam, Satyanarayana: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity. Journal of Computer and System Sciences 63(3), 449–473 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Lokam, Satyanarayana: Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1–2), 1–155 (2009)

    MathSciNet  MATH  Google Scholar 

  • Ilan Newman (1991). Private vs. Common Random Bits in Communication Complexity. Information Processing Letters 39(2), 67–71.

  • Noam Nisan & Avi Wigderson: Hardness vs. Randomness. Journal of Computer and System Sciences 49(2), 149–167 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Ryan O'Donnell & A. C. Cem Say (2016). The Weakness of CTC Qubits and the Power of Approximate Counting. Technical Report TR16-147, Electronic Colloquium on Computational Complexity (ECCC). URL http://eccc.hpi-web.de/report/2016/147/.

  • Christos Papadimitriou & Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). Journal of Computer and System Sciences 28(2), 244–259 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  • Periklis Papakonstantinou, Dominik Scheder & Hao Song (2014). Overlays and Limited Memory Communication. In Proceedings of the 29th Conference on Computational Complexity (CCC), 298–308. IEEE.

  • Ramamohan Paturi & Janos Simon: Probabilistic Communication Complexity. Journal of Computer and System Sciences 33(1), 106–123 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  • Pudlák, Pavel, Rödl, Vojtech, Savický, Petr: Graph Complexity. Acta Informatica 25(5), 515–535 (1988)

    MathSciNet  MATH  Google Scholar 

  • Ran Raz & Amir Shpilka (2004). On the Power of Quantum Proofs. In Proceedings of the 19th Conference on Computational Complexity (CCC), 260–274. IEEE.

  • Razborov, Alexander: On Rigid Matrices. Technical report, Steklov Mathematical Institute (1989). In Russian

    Google Scholar 

  • Razborov, Alexander: On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 385–390 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  • Alexander Razborov & Alexander Sherstov: The Sign-Rank of \({\rm AC}^0\). SIAM Journal on Computing 39(5), 1833–1855 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Alexander Russell & Ravi Sundaram: Symmetric Alternation Captures BPP. Computational Complexity 7(2), 152–162 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  • Sherstov, Alexander: Halfspace Matrices. Computational Complexity 17(2), 149–178 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Sherstov, Alexander: The Pattern Matrix Method. SIAM Journal on Computing 40(6), 1969–2000 (2011a)

    Article  MathSciNet  MATH  Google Scholar 

  • Sherstov, Alexander: The Unbounded-Error Communication Complexity of Symmetric Functions. Combinatorica 31(5), 583–614 (2011b)

    Article  MathSciNet  MATH  Google Scholar 

  • Toda, Seinosuke: PP is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing 20(5), 865–877 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  • Tripathi, Rahul: The 1-Versus-2 Queries Problem Revisited. Theory of Computing Systems 46(2), 193–221 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Leslie Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science (MFCS), 162–176. Springer.

  • Leslie Valiant & Vijay Vazirani: NP is as Easy as Detecting Unique Solutions. Theoretical Computer Science 47(3), 85–93 (1986)

    MathSciNet  MATH  Google Scholar 

  • Nikolai Vereshchagin (1995). Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. In Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (ISTCS), 46–51. IEEE.

  • Nikolai Vereshchagin (1999). Relativizability in Complexity Theory. In Provability, Complexity, Grammars, volume 192 of AMS Translations, Series 2, 87–172. American Mathematical Society.

  • Wunderlich, Henning: On a Theorem of Razborov. Computational Complexity 21(3), 431–477 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Harvard University, Cambridge, USA

    Mika Göös

  2. University of Toronto, Toronto, Canada

    Toniann Pitassi

  3. University of Memphis, Memphis, USA

    Thomas Watson

Authors
  1. Mika Göös
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Toniann Pitassi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thomas Watson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Watson.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Göös, M., Pitassi, T. & Watson, T. The Landscape of Communication Complexity Classes. comput. complex. 27, 245–304 (2018). https://doi.org/10.1007/s00037-018-0166-6

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-018-0166-6

Keywords

Subject classification

Search

Navigation