A composition theorem for decision tree complexity

2013/02/18 by Ashley Montanaro, Montanaro, Ashley · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1302.4207

openalex publication_date 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We completely characterise the complexity in the decision tree model of computing composite relations of the form h = g(f¹,...,fⁿ), where each relation fⁱ is boolean-valued. Immediate corollaries include a direct sum theorem for decision tree complexity and a tight characterisation of the decision tree complexity of iterated boolean functions.

Citations

• Tight adversary bounds for composite functions

Cited by

• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Related

• Decision Tree Complexity versus Block Sensitivity and Degree
• On (Simple) Decision Tree Rank
• Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
• Conflict complexity is lower bounded by block sensitivity
• Truth Table Minimization of Computational Models