Document Open Access Logo

A Composition Theorem for Conical Juntas

Authors Mika Göös, T. S. Jayram

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.5.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Mika Göös
T. S. Jayram

Cite As Get BibTex

Mika Göös and T. S. Jayram. A Composition Theorem for Conical Juntas. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.5

Abstract

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

- AND-OR trees. We show a near-optimal ~Omega(n^{0.753...}) randomised communication lower bound for the recursive NAND function (a.k.a. AND-OR tree). This answers an open question posed by Beame and Lawry.

- Majority trees. We show an Omega(2.59^k) randomised communication lower bound for the 3-majority tree of height k. This improves over the state-of-the-art already in the context of randomised decision tree complexity.

Subject Classification

Keywords
  • Composition theorems
  • conical juntas

Metrics

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

References

  1. Kazuyuki Amano. Bounding the randomized decision tree complexity of read-once boolean functions. In Proceedings of the 22nd Symposium on Discrete Algorithms (SODA), pages 1729-1744. SIAM, 2011. Google Scholar
  2. Kazuyuki Amano. On directional vs. general randomized decision tree complexity for read-once formulas. Chicago Journal of Theoretical Computer Science, 2011(3), 2011. URL: http://dx.doi.org/10.4086/cjtcs.2011.003.
  3. Kazuyuki Amano. Researching the complexity of boolean functions with computers. Bulletin of EATCS, 101:64-91, 2014. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/181.
  4. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Technical Report TR15-098, Electronic Colloquium on Computational Complexity (ECCC), 2015. URL: http://eccc.hpi-web.de/report/2015/098/.
  5. Andris Ambainis, Andrew Childs, Ben Reichardt, Robert Špalek, and Shengyu Zhang. Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. SIAM Journal on Computing, 39(6):2513-2530, 2010. URL: http://dx.doi.org/10.1137/080712167.
  6. Paul Beame and Joan Lawry. Randomized versus nondeterministic communication complexity. In Proceedings of the 24th Symposium on Theory of Computing (STOC), pages 188-199. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129732.
  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. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00144-X.
  9. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Information and Computation, 243:2-25, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.003.
  10. Siu On Chan, James Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 350-359. IEEE, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.45.
  11. Ehud Friedgut, Jeff Kahn, and Avi Wigderson. Computing graph properties by randomized subcube partitions. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM), pages 105-113. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45726-7_9.
  12. 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.
  13. 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), pages 257-266. ACM, 2015. (Full version: http://eccc.hpi-web.de/report/2014/147/). URL: http://dx.doi.org/10.1145/2746539.2746596.
  14. 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.
  15. 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.
  16. Rahul Jain, Hartmut Klauck, and Shengyu Zhang. Depth-independent lower bounds on the communication complexity of read-once boolean formulas. In Proceedings of the 16th International Computing and Combinatorics Conference (COCOON), pages 54-59. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14031-0_8.
  17. 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.
  18. 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, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.39.
  19. 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.
  20. 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.
  21. 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), Leibniz International Proceedings in Informatics (LIPIcs), pages 915-930. Schloss Dagstuhl, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.915.
  22. Itamar Landau, Asaf Nachmias, Yuval Peres, and Sithparran Vanniasegaram. The lower bound for evaluating a recursive ternary majority function: an entropy-free proof. Technical report, U.C. Berkeley, 2006. Google Scholar
  23. Joan Lawry. Communication complexity: Iterative techniques for lower bounds. PhD thesis, University of Washington, 1993. UW-CSE-93-3-04. Google Scholar
  24. James Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of the 47th Symposium on Theory of Computing (STOC), pages 567-576. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746599.
  25. Nikos Leonardos. An improved lower bound for the randomized decision tree complexity of recursive majority. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 696-708. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_59.
  26. 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.
  27. Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, and David Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. Random Structures &Algorithms, 2015. In press. URL: http://dx.doi.org/10.1002/rsa.20598.
  28. Michael Saks and Avi Wigderson. Probabilistic boolean decision trees and the complexity of evaluating game trees. In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), pages 29-38. IEEE, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.44.
  29. Miklos Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures &Algorithms, 6(1):75-87, 1995. URL: http://dx.doi.org/10.1002/rsa.3240060108.
  30. 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/.
  31. Alexander Sherstov. Approximating the AND-OR tree. Theory of Computing, 9(20):653-663, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a020.
  32. Alexander Sherstov. Breaking the Minsky-Papert barrier for constant-depth circuits. In Proceedings of the 46th Symposium on Theory of Computing (STOC), pages 223-232. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591871.
  33. Marc Snir. Lower bounds on probabilistic linear decision trees. Theoretical Computer Science, 38:69-82, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90210-5.
  34. Nikolai Vereshchagin. Randomized boolean decision trees: Several remarks. Theoretical Computer Science, 207(2):329-342, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(98)00071-1.
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