Document Open Access Logo

The Landscape of Communication Complexity Classes

Authors Mika Göös, Toniann Pitassi, Thomas Watson

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.86.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Mika Göös
Toniann Pitassi
Thomas Watson

Cite As Get BibTex

Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.86

Abstract

We 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 !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 intersect coAM, for which it is notoriously open to prove any explicit lower bounds. We also prove that US !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 !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.

Subject Classification

Keywords
  • Landscape
  • communication
  • complexity
  • classes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. URL: http://dx.doi.org/10.1098/rspa.2005.1546.
  2. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1), 2009. URL: http://dx.doi.org/10.1145/1490270.1490272.
  3. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), pages 337-347. IEEE, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.15.
  4. Andreas Blass and Yuri Gurevich. On the unique satisfiability problem. Information and Control, 55(1-3):80-88, 1982. URL: http://dx.doi.org/10.1016/S0019-9958(82)90439-9.
  5. Harry Buhrman, Nikolai Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In Proceedings of the 22nd Conference on Computational Complexity (CCC), pages 24-32. IEEE, 2007. URL: http://dx.doi.org/10.1109/CCC.2007.18.
  6. Jin-Yi Cai and Venkatesan Chakaravarthy. On zero error algorithms having oracle access to one query. Journal of Combinatorial Optimization, 11(2):189-202, 2006. URL: http://dx.doi.org/10.1007/s10878-006-7130-0.
  7. Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler. Annotations for sparse data streams. In Proceedings of the 25th Symposium on Discrete Algorithms (SODA), pages 687-706. ACM-SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.52.
  8. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Transactions on Algorithms, 11(1):7, 2014. URL: http://dx.doi.org/10.1145/2636924.
  9. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable stream computation and Arthur-Merlin communication. In Proceedings of the 30th Computational Complexity Conference (CCC). Schloss Dagstuhl, 2015. To appear. Google Scholar
  10. Richard Chang, Jim Kadin, and Pankaj Rohatgi. On unique satisfiability and the threshold behavior of randomized reductions. Journal of Computer and System Sciences, 50(3):359-373, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1028.
  11. Richard Chang and Suresh Purini. Amplifying ZPP^\MakeUppercasesat[1] and the two queries problem. In Proceedings of the 23rd Conference on Computational Complexity (CCC), pages 41-52. IEEE, 2008. URL: http://dx.doi.org/10.1109/CCC.2008.32.
  12. Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauriere, and Jérémie Roland. Relative discrepancy does not separate information and communication complexity. Technical Report TR15-028, Electronic Colloquium on Computational Complexity (ECCC), 2015. Google Scholar
  13. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4):612-625, 2002. URL: http://dx.doi.org/10.1016/S0022-0000(02)00019-3.
  14. Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication for boolean functions. In Proceedings of the 47th Symposium on Theory of Computing (STOC). ACM, 2015. To appear. Google Scholar
  15. Dmitry Gavinsky and Shachar Lovett. 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), pages 514-524. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_43.
  16. Dmitry Gavinsky and Alexander Sherstov. A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6(1):227-245, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a010.
  17. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. In Proceedings of the 47th Symposium on Theory of Computing (STOC). ACM, 2015. To appear. Google Scholar
  18. Mika Göös and Thomas Watson. Communication complexity of set-disjointness for all probabilities. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), pages 721-736. Schloss Dagstuhl, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.721.
  19. Tom Gur and Ran Raz. Arthur-Merlin streaming complexity. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 528-539. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_45.
  20. Tom Gur and Ron Rothblum. Non-interactive proofs of proximity. In Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS), pages 133-142. ACM, 2015. URL: http://dx.doi.org/10.1145/2688073.2688079.
  21. Bernd Halstenberg and Rüdiger Reischuk. Relations between communication complexity classes. Journal of Computer and System Sciences, 41(3):402-429, 1990. URL: http://dx.doi.org/10.1016/0022-0000(90)90027-I.
  22. Yenjo Han, Lane Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. SIAM Journal on Computing, 26(1):59-78, 1997. URL: http://dx.doi.org/10.1137/S0097539792240467.
  23. Russell Impagliazzo and Ryan Williams. Communication complexity with synchronized clocks. In Proceedings of the 25th Conference on Computational Complexity (CCC), pages 259-269. IEEE, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.32.
  24. T.S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), pages 673-682. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780640.
  25. Stasys Jukna. On graph complexity. Combinatorics, Probability, & Computing, 15(6):855-876, 2006. URL: http://dx.doi.org/10.1017/S0963548306007620.
  26. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  27. Volker Kaibel and Stefan Weltge. A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete &Computational Geometry, 53(2):397-401, 2015. URL: http://dx.doi.org/10.1007/s00454-014-9655-9.
  28. Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In Proceedings of the 18th Conference on Computational Complexity (CCC), pages 118-134. IEEE, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214415.
  29. Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20-46, 2007. URL: http://dx.doi.org/10.1137/S0097539702405620.
  30. Hartmut Klauck. On Arthur Merlin games in communication complexity. In Proceedings of the 26th Conference on Computational Complexity (CCC), pages 189-199. IEEE, 2011. URL: http://dx.doi.org/10.1109/CCC.2011.33.
  31. Hartmut Klauck and Ved Prakash. Streaming computations with a loquacious prover. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), pages 305-320. ACM, 2013. URL: http://dx.doi.org/10.1145/2422436.2422471.
  32. Hartmut Klauck and Ved Prakash. An improved interactive streaming algorithm for the distinct elements problem. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 919-930. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_76.
  33. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  34. Tak Wah Lam and Walter Ruzzo. Results on communication complexity classes. Journal of Computer and System Sciences, 44(2):324-342, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90025-E.
  35. Nathan Linial and Adi Shraibman. Learning complexity vs communication complexity. Combinatorics, Probability, & Computing, 18(1-2):227-245, 2009. URL: http://dx.doi.org/10.1017/S0963548308009656.
  36. Satyanarayana Lokam. 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. URL: http://dx.doi.org/10.1006/jcss.2001.1786.
  37. Satyanarayana Lokam. Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science, 4(1-2):1-155, 2009. URL: http://dx.doi.org/10.1561/0400000011.
  38. Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67-71, 1991. URL: http://dx.doi.org/10.1016/0020-0190(91)90157-D.
  39. Christos Papadimitriou and Mihalis Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244-259, 1984. URL: http://dx.doi.org/10.1016/0022-0000(84)90068-0.
  40. Periklis Papakonstantinou, Dominik Scheder, and Hao Song. Overlays and limited memory communication. In Proceedings of the 29th Conference on Computational Complexity (CCC), pages 298-308. IEEE, 2014. URL: http://dx.doi.org/10.1109/CCC.2014.37.
  41. Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106-123, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90046-2.
  42. Pavel Pudlák, Vojtech Rödl, and Petr Savický. Graph complexity. Acta Informatica, 25(5):515-535, 1988. URL: http://dx.doi.org/10.1007/BF00279952.
  43. Ran Raz and Amir Shpilka. On the power of quantum proofs. In Proceedings of the 19th Conference on Computational Complexity (CCC), pages 260-274. IEEE, 2004. URL: http://dx.doi.org/10.1109/CCC.2004.1313849.
  44. Alexander Razborov. On rigid matrices. Technical report, Steklov Mathematical Institute, 1989. In Russian. Google Scholar
  45. Alexander Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90260-M.
  46. Alexander Razborov and Alexander Sherstov. The sign-rank of AC⁰. SIAM Journal on Computing, 39(5):1833-1855, 2010. URL: http://dx.doi.org/10.1137/080744037.
  47. Alexander Sherstov. Halfspace matrices. Computational Complexity, 17(2):149-178, 2008. URL: http://dx.doi.org/10.1007/s00037-008-0242-4.
  48. Alexander Sherstov. The unbounded-error communication complexity of symmetric functions. Combinatorica, 31(5):583-614, 2011. URL: http://dx.doi.org/10.1007/s00493-011-2580-0.
  49. Rahul Tripathi. The 1-versus-2 queries problem revisited. Theory of Computing Systems, 46(2):193-221, 2010. URL: http://dx.doi.org/10.1007/s00224-008-9126-x.
  50. Leslie Valiant. Graph-theoretic arguments in low-level complexity. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science (MFCS), pages 162-176. Springer, 1977. URL: http://dx.doi.org/10.1007/3-540-08353-7_135.
  51. Leslie Valiant and Vijay Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(3):85-93, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90135-0.
  52. Nikolai Vereshchagin. Relativizability in complexity theory. In Provability, Complexity, Grammars, volume 192 of AMS Translations, Series 2, pages 87-172. American Mathematical Society, 1999. Google Scholar
  53. Henning Wunderlich. On a theorem of Razborov. Computational Complexity, 21(3):431-477, 2012. URL: http://dx.doi.org/10.1007/s00037-011-0021-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact