Separating Decision Tree Complexity from Subcube Partition Complexity

Authors Robin Kothari, David Racicot-Desloges, Miklos Santha



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.915.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Robin Kothari
David Racicot-Desloges
Miklos Santha

Cite As Get BibTex

Robin Kothari, David Racicot-Desloges, and Miklos Santha. Separating Decision Tree Complexity from Subcube Partition Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 915-930, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.915

Abstract

The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose deterministic subcube partition complexity is asymptotically smaller than its randomized decision tree complexity, resolving an open problem of Friedgut, Kahn, and Wigderson (2002). Our lower bound is based on the information-theoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function.

We also show that the public-coin partition bound, the best known lower bound method for randomized decision tree complexity subsuming other general techniques such as block sensitivity, approximate degree, randomized certificate complexity, and the classical adversary bound, also lower bounds randomized subcube partition complexity. This shows that all these lower bound techniques cannot prove optimal lower bounds for randomized decision tree complexity, which answers an open question of Jain and Klauck (2010) and Jain, Lee, and Vishnoi (2014).

Subject Classification

Keywords
  • Decision tree complexity
  • query complexity
  • randomized algorithms
  • subcube partition complexity

Metrics

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

References

  1. S. Aaronson. Quantum certificate complexity. SIAM Journal on Computing, 35(4):804-824, 2006. Google Scholar
  2. S. Aaronson. Lower bounds for local search by quantum arguments. Journal of Computer and System Sciences, 74(3):313-332, 2008. Google Scholar
  3. A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs. Separations in query complexity based on pointer functions. arXiv preprint http://arxiv.org/abs/arXiv:1506.04719, 2015. Google Scholar
  4. Y. Brandman, A. Orlitsky, and J. Hennessy. A spectral lower bound technique for the size of decision trees and two-level AND/OR circuits. IEEE Transactons on Computers, 39(2):282-287, February 1990. Google Scholar
  5. H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. Google Scholar
  6. S. Chakraborty, R. Kulkarni, S. V. Lokam, and N. Saurabh. Upper bounds on Fourier entropy. Electronic Colloquium on Computational Complexity (ECCC), 20:52, 2013. Google Scholar
  7. E. Friedgut, J. Kahn, and A. Wigderson. Computing graph properties by randomized subcube partitions. In Randomization and Approximation Techniques in Computer Science, volume 2483 of Lecture Notes in Computer Science, pages 105-113. Springer Berlin Heidelberg, 2002. Google Scholar
  8. M. Göös, T. Pitassi, and T. Watson. Deterministic communication vs. partition number. To appear in the Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), 2015. Google Scholar
  9. R. Jain and H. Klauck. The partition bound for classical communication complexity and query complexity. In Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity, CCC'10, pages 247-258, 2010. Google Scholar
  10. R. Jain, T. Lee, and N. Vishnoi. A quadratically tight partition bound for classical communication complexity and query complexity. arXiv preprint http://arxiv.org/abs/arXiv:1401.4512, 2014. Google Scholar
  11. T. S. Jayram, R. Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing (STOC), STOC'03, pages 673-682, New York, NY, USA, 2003. ACM. Google Scholar
  12. S. Jukna. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Springer, 2012. Google Scholar
  13. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 2006. Google Scholar
  14. I. Landau, A. Nachmias, Y. Peres, and S. Vanniasegaram. The lower bound for evaluating a recursive ternary majority function: an entropy-free proof. Undergraduate Research Reports, Department of Statistics, University of California, Berkeley, 2006. Google Scholar
  15. S. Laplante and F. Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM Journal on Computing, 38(1):46-62, 2008. Google Scholar
  16. A. Montanaro. A composition theorem for decision tree complexity. Chicago Journal of Theoretical Computer Science, 2014(6), July 2014. Google Scholar
  17. N. Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999-1007, 1991. Google Scholar
  18. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 15(4):557-565, 1995. Google Scholar
  19. A. L. Rosenberg. On the time required to recognize properties of graphs: a problem. SIGACT News, 5(4):15-16, 1973. Google Scholar
  20. M. Saks and A. Wigderson. Probabilistic boolean decision trees and the complexity of evaluating game trees. Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS), pages 29-38, 1986. Google Scholar
  21. P. Savický. On determinism versus unambiguous nondeterminism for decision trees. ECCC, TR02-009, 2002. Google Scholar
  22. R. Špalek and M. Szegedy. All quantum adversary methods are equivalent. Theory of Computing, 2(1):1-18, 2006. Google Scholar
  23. A. Tal. Properties and applications of boolean function composition. In Proc. of the 4th Conf. on Innovations in Theoretical Computer Science, ITCS'13, pages 441-454, 2013. Google Scholar
  24. A. Yao. Probabilistic computations: Toward a unified measure of complexity. Proc. of the 18th IEEE Symp. on Foundations of Computer Science (FOCS), pages 222-227, 1977. Google Scholar
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