Document Open Access Logo

On (Simple) Decision Tree Rank

Authors Yogesh Dahiya, Meena Mahajan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.15.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Yogesh Dahiya
  • The Institute of Mathematical Sciences (HBNI), Chennai, India
Meena Mahajan
  • The Institute of Mathematical Sciences (HBNI), Chennai, India

Cite AsGet BibTex

Yogesh Dahiya and Meena Mahajan. On (Simple) Decision Tree Rank. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.15

Abstract

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure is also studied, but to a lesser extent. Another decision tree measure that has received very little attention is the minimal rank of the decision tree, first introduced by Ehrenfeucht and Haussler in 1989. This measure is not polynomially related to depth, and hence it can reveal additional information about the complexity of a function. It is characterised by the value of a Prover-Delayer game first proposed by Pudlák and Impagliazzo in the context of tree-like resolution proofs. In this paper we study this measure further. We obtain upper and lower bounds on rank in terms of (variants of) certificate complexity. We also obtain upper and lower bounds on the rank for composed functions in terms of the depth of the outer function and the rank of the inner function. We compute the rank exactly for several natural functions and use them to show that all the bounds we have obtained are tight. We also observe that the size-rank relationship for decision trees, obtained by Ehrenfeucht and Haussler, is tight upto constant factors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
Keywords
  • Boolean functions
  • Decision trees
  • certificate complexity
  • rank

Metrics

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

References

  1. James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo. k^+ decision trees - (extended abstract). In 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS, volume 6451 of Lecture Notes in Computer Science, pages 74-88. Springer, 2010. full version on author’s webpage, http://www.cs.cmu.edu/ odonnell/papers/k-plus-dts.pdf. URL: https://doi.org/10.1007/978-3-642-16988-5_7.
  2. Eli Ben-Sasson, Russell Impagliazzo, and Avi Wigderson. Near optimal separation of tree-like and general resolution. Combinatorica, 24(4):585-603, 2004. URL: https://doi.org/10.1007/s00493-004-0036-5.
  3. Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. A characterization of tree-like resolution size. Information Processing Letters, 113(18):666-671, 2013. URL: https://doi.org/10.1016/j.ipl.2013.06.002.
  4. Avrim Blum. Rank-r decision trees are a subclass of r-decision lists. Information Processing Letters, 42(4):183-185, 1992. URL: https://doi.org/10.1016/0020-0190(92)90237-P.
  5. Manuel Blum and Russell Impagliazzo. Generic oracles and oracle classes. In 28th Annual Symposium on Foundations of Computer Science (FOCS), pages 118-126. IEEE, 1987. Google Scholar
  6. Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82(3):231-246, 1989. URL: https://doi.org/10.1016/0890-5401(89)90001-1.
  7. Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief history of Strahler numbers. In Language and Automata Theory and Applications - 8th International Conference LATA, volume 8370 of Lecture Notes in Computer Science, pages 1-13. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-04921-2_1.
  8. Juan Luis Esteban and Jacobo Torán. A combinatorial characterization of treelike resolution space. Information Processing Letters, 87(6):295-300, 2003. Google Scholar
  9. Juris Hartmanis and Lane A Hemachandra. One-way functions and the nonisomorphism of NP-complete sets. Theoretical Computer Science, 81(1):155-163, 1991. Google Scholar
  10. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  11. Oliver Kullmann. Investigating a general hierarchy of polynomially decidable classes of CNF’s based on short tree-like resolution proofs. Electron. Colloquium Comput. Complex., 41, 1999. URL: http://eccc.hpi-web.de/eccc-reports/1999/TR99-041/index.html.
  12. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  13. Ashley Montanaro. A composition theorem for decision tree complexity. Chicago Journal of Theoretical Computer Science, 2014(6), July 2014. Google Scholar
  14. Pavel Pudlák and Russell Impagliazzo. A lower bound for DLL algorithms for k-SAT (preliminary version). In Proceedings of the eleventh annual ACM-SIAM Symposium on Discrete Algorithms SODA, pages 128-136, 2000. Google Scholar
  15. Gábor Tardos. Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A? Combinatorica, 9(4):385-392, 1989. Google Scholar
  16. György Turán and Farrokh Vatan. Linear decision lists and partitioning algorithms for the construction of neural networks. In Foundations of Computational Mathematics, pages 414-423, Berlin, Heidelberg, 1997. Springer. Google Scholar
  17. Kei Uchizawa and Eiji Takimoto. Lower bounds for linear decision trees with bounded weights. In 41st International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM, volume 8939 of Lecture Notes in Computer Science, pages 412-422. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46078-8_34.
  18. Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. URL: https://doi.org/10.1145/1968.1972.
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 Imprint Privacy Contact