License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.15
URN: urn:nbn:de:0030-drops-155263
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15526/
Dahiya, Yogesh ;
Mahajan, Meena
On (Simple) Decision Tree Rank
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.
BibTeX - Entry
@InProceedings{dahiya_et_al:LIPIcs.FSTTCS.2021.15,
author = {Dahiya, Yogesh and Mahajan, Meena},
title = {{On (Simple) Decision Tree Rank}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15526},
URN = {urn:nbn:de:0030-drops-155263},
doi = {10.4230/LIPIcs.FSTTCS.2021.15},
annote = {Keywords: Boolean functions, Decision trees, certificate complexity, rank}
}
|
Keywords: |
|
Boolean functions, Decision trees, certificate complexity, rank |
|
Collection: |
|
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
29.11.2021 |
