Document Open Access Logo

Randomized Communication vs. Partition Number

Authors Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

Mika Göös
T. S. Jayram
Toniann Pitassi
Thomas Watson

Cite As Get BibTex

Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication vs. Partition Number. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.52

Abstract

We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Goos, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.

Subject Classification

Keywords
  • communication complexity
  • partition number
  • information complexity

Metrics

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

References

  1. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Symposium on Theory of Computing (STOC), pages 863-876. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897644.
  2. Alfred Aho, Jeffrey Ullman, and Mihalis Yannakakis. On notions of information transfer in VLSI circuits. In Proceedings of the 15th Symposium on Theory of Computing (STOC), pages 133-139. ACM, 1983. URL: http://dx.doi.org/10.1145/800061.808742.
  3. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. In Proceedings of the 48th Symposium on Theory of Computing (STOC), pages 800-813. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897524.
  4. Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly optimal separations between communication (or query) complexity and partitions. In Proceedings of the 31st Computational Complexity Conference (CCC), pages 4:1-4:14. Schloss Dagstuhl, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.4.
  5. Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha. Separations in communication complexity using cheat sheets and information complexity. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 555-564. IEEE, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.66.
  6. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.006.
  7. Aleksandrs Belovs. Non-intersecting complexity. In Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 158-165. Springer, 2006. URL: http://dx.doi.org/10.1007/11611257_13.
  8. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.05.001.
  9. Mark Braverman. Interactive information complexity. SIAM Journal on Computing, 44(6):1698-1739, 2015. URL: http://dx.doi.org/10.1137/130938517.
  10. Mark Braverman and Omri Weinstein. An interactive information odometer and applications. In Proceedings of the 47th Symposium on Theory of Computing (STOC), pages 341-350. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746548.
  11. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM, 62(2):17:1-17:23, 2015. URL: http://dx.doi.org/10.1145/2716307.
  12. 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.
  13. Mika Göös. Lower bounds for clique vs. independent set. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS), pages 1066-1076. IEEE, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.69.
  14. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication vs. partition number. Technical Report TR15-169, Electronic Colloquium on Computational Complexity (ECCC), 2015. URL: https://eccc.weizmann.ac.il/report/2015/169/.
  15. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835-1869, 2016. URL: http://dx.doi.org/10.1137/15M103145X.
  16. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS), pages 1077-1088. IEEE, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.70.
  17. Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. In Proceedings of the 25th Conference on Computational Complexity (CCC), pages 247-258. IEEE, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.31.
  18. Rahul Jain, Hartmut Klauck, and Miklos Santha. Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters, 110(20):893-897, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.07.020.
  19. Rahul Jain, Troy Lee, and Nisheeth Vishnoi. A quadratically tight partition bound for classical communication complexity and query complexity. Technical report, arXiv, 2014. URL: http://arxiv.org/abs/1401.4512.
  20. T.S. Jayram, Swastik Kopparty, and Prasad Raghavendra. On the communication complexity of read-once AC⁰ formulae. In Proceedings of the 24th Conference on Computational Complexity (CCC), pages 329-340. IEEE, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.39.
  21. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  22. Jedrzej Kaniewski, Troy Lee, and Ronald de Wolf. Query complexity in expectation. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 761-772. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_62.
  23. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, and David Xiao. Lower bounds on information complexity via zero-communication protocols and applications. SIAM Journal on Computing, 44(5):1550-1572, 2015. URL: http://dx.doi.org/10.1137/130928273.
  24. Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 701-712. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_58.
  25. Robin Kothari, David Racicot-Desloges, and Miklos Santha. Separating decision tree complexity from subcube partition complexity. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM), pages 915-930. Schloss Dagstuhl, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.915.
  26. Eyal Kushilevitz. Unpublished. Cited in [32], 1994. Google Scholar
  27. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  28. Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-399, 2007. URL: http://dx.doi.org/10.1561/0400000040.
  29. Nikos Leonardos and Michael Saks. Lower bounds on the randomized communication complexity of read-once functions. Computational Complexity, 19(2):153-181, 2010. URL: http://dx.doi.org/10.1007/s00037-010-0292-2.
  30. László Lovász and Michael Saks. Lattices, Möbius functions and communication complexity. In Proceedings of the 29th Symposium on Foundations of Computer Science (FOCS), pages 81-90. IEEE, 1988. URL: http://dx.doi.org/10.1109/SFCS.1988.21924.
  31. Sagnik Mukhopadhyay and Swagato Sanyal. Towards better separation between deterministic and randomized query complexity. In Proceedings of 35th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 206-220. Schloss Dagstuhl, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.206.
  32. Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15(4):557-565, 1995. URL: http://dx.doi.org/10.1007/BF01192527.
  33. Petr Savický. On determinism versus unambiguous nondeterminism for decision trees. Technical Report TR02-009, Electronic Colloquium on Computational Complexity (ECCC), 2002. URL: http://eccc.hpi-web.de/report/2002/009/.
  34. Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441-466, 1991. URL: http://dx.doi.org/10.1016/0022-0000(91)90024-Y.
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