Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YOGESH DAHIYA:
All reports by Author Yogesh Dahiya:

TR22-001 | 28th December 2021
Yogesh Dahiya, Meena Mahajan

On (Simple) Decision Tree Rank

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 ... more >>>




ISSN 1433-8092 | Imprint