Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Decision Trees and Branching Programs

Thomas Watson

Published Oct 9, 2026• 0 citations
Publisher

Abstract

This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.

DOI
10.1017/9781009752329.021

Related papers

Models of Query Complexity for Boolean Functions

Sourav Chakraborty

In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially

•Aug 6, 2010•0 citations

Certification complexity of Boolean functions

Chandrima Kayal, Sophie Laplante, Émile Larroque +2 more

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

arXiv:2609.26757•Sep 22, 2026•0 citations

Approximate Query Complexity

Clifford Smyth

Let f : {0, 1} n → {0, 1}. Let μ be a product probability measure on {0, 1} n . For ϵ ≥ 0, we define Dϵ ( f ), the ϵ-approximate decision tree complexity of f , to be the minimum depth of a decision tree T with μ ( T ( x ) ≠ f ( x )) ≤ ϵ . For j = 0 or 1 and for δ ≥ 0, we define Cj,δ ( f ), the δ-approximate j -certificate complexity of f , to be the minimum certificate complexity of a set A ⊆ Ω with μ ( AΔf −1 ( j )) ≤ ϵ . Note that if μ ( x ) > 0 for all x then D 0 ( f ) = D ( f ) and Cj ,0 ( f ) = Cj ( f ) are the ordinary decision tree and j -certificate complexities of f , respectively. We extend the well-known result, D ( f ) ≤ C 1 ( f ) C 0 ( f ) [Blum and Impagliazzo 1987; Hartmanis and Hemachandra 1991; Tardos 1989], proving that for all ϵ > 0 there exists a δ > 0 and a constant K = K ( ϵ , δ ) > 0 such that for all n , μ , f , Dϵ ( f ) ≤ K C 1, δ ( f ) C 0, δ ( f ). We also give a partial answer to a related question on query complexity raised by Tardos [1989]. We prove generalizations of these results to general product probability spaces.

ACM Transactions on Computation Theory•Aug 1, 2011•0 citations

Lower bounds on quantum query complexity for read-once decision trees with parity nodes

Hideaki Fukuhara, Eiji Takimoto

We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.

Computing: The Australasian Theory Symposium•Jan 1, 2009•0 citations

Sensitivity and Query Complexity under Uncertainty

Benson, Deepu, Komarath, Balagopal, Nikhil S. Mande +3 more

In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

arXiv:2507.00148•Jun 30, 2025•0 citations

The Information Complexity of Decision Trees

Avantika Agarwal, Shalev Ben-David, Eric Blais

We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

arXiv:2609.12164•Sep 10, 2026•0 citations
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
Certificate complexity (C(f))(C(f ))(C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity (D)(D)(D) and other query models such as bounded-error randomized and quantum complexity (R,Q)(R, Q)(R,Q), but not as well for quantum zero-error (Q0)(Q_0)(Q0​) and exact query complexity (QE)(Q_E)(QE​), where there is no agreed-upon certificate 'object' (even for QQQ). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of C,RCC, RCC,RC (randomized certificate complexity) and QCQCQC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on QEQ_EQE​ and Q0Q_0Q0​, the quantum analogues of DDD and R0R_0R0​, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for Q0Q_0Q0​, but rational degree and QQQ are asymptotically smaller.
Let f : {0, 1} n → {0, 1}. Let μ be a product probability measure on {0, 1} n . For ϵ ≥ 0, we define Dϵ ( f ), the ϵ-approximate decision tree complexity of f , to be the minimum depth of a decision tree T with μ ( T ( x ) ≠ f ( x )) ≤ ϵ . For j = 0 or 1 and for δ ≥ 0, we define Cj,δ ( f ), the δ-approximate j -certificate complexity of f , to be the minimum certificate complexity of a set A ⊆ Ω with μ ( AΔf −1 ( j )) ≤ ϵ . Note that if μ ( x ) > 0 for all x then D 0 ( f ) = D ( f ) and Cj ,0 ( f ) = Cj ( f ) are the ordinary decision tree and j -certificate complexities of f , respectively. We extend the well-known result, D ( f ) ≤ C 1 ( f ) C 0 ( f ) [Blum and Impagliazzo 1987; Hartmanis and Hemachandra 1991; Tardos 1989], proving that for all ϵ > 0 there exists a δ > 0 and a constant K = K ( ϵ , δ ) > 0 such that for all n , μ , f , Dϵ ( f ) ≤ K C 1, δ ( f ) C 0, δ ( f ). We also give a partial answer to a related question on query complexity raised by Tardos [1989]. We prove generalizations of these results to general product probability spaces.
We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.
In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).