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).
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).
The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 - ε in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αεTk-query algorithm has success probability at most (2αε(1 - ε))kin computing the fc-fold direct product f⊗kcorrectly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α >; 0, the worst-case success probability of any αR2(f)k-query randomized algorithm for f⊗kfalls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collec tion of martingales associated with an algorithm attempting to solve f⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing n copies of a function f, even with a small success probability of γn, requires Θ(n) times the "maximum distributional" query complexity of f with success parameter γ. This result holds for all success parameters γ, even when γ is very close to 1/2 or to 1. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for γ bounded away from 21 and 1 as well as the strong direct sum theorem of Blais and Brody (2019) for γ≈1−1/n. The second establishes a general "list decoding" direct product theorem that captures many different variants of partial computation tasks related to the function fn consisting of n copies of f. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call "discounted score". We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.
We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing n copies of a function f, even with a small success probability of γn, requires Θ(n) times the maximum distributional query complexity of f with success parameter γ. This result holds for all success parameters γ, even when γ is very close to 1/2 or to 1. As a result, it unifies and generalizes Drucker’s direct product theorem (2012) for γ bounded away from 21 and 1 as well as the strong direct sum theorem of Blais and Brody (2019) for γ≈1−1/n. The second establishes a general list decoding direct product theorem that captures many different variants of “partial computation” tasks related to the function fn consisting of n copies of f. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call discounted score. We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expected randomized query complexity. For any total relation f and any error tolerance ε∈[0,1], we prove limn→∞nRε(fn)=(1−ε)R0(f). Thus the amortization converts bounded-error into zero error with the exact multiplicative factor 1−ε. We also prove corresponding liminf/limsup bounds for worst-case randomized and distributional query complexity. These results improve prior direct-sum bounds that were known only up to constant factors or in restricted error regimes, and they resolve an open question posed by Blais and Brody (2019). Additionally for one-sided computation of the function ORn∘f, we obtain analogous exact amortized identities for both expected and worst-case cost. As applications, we obtain separations between amortized and single-instance costs, including unbounded separations for distributional complexity and randomized relations, and a quadratic barrier for randomized total functions.
Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform. A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately? This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines. We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation. In more detail, we make contributions in the following areas:
Improved product theorems for randomized query complexity: The direct product problem seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 – e in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αeTk-query algorithm has success probability at most (2αe(1 – e))k in computing the k-fold product f ⊗k correctly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α > 0, the worst-case success probability of any αR 2(f)k-query randomized algorithm for f⊗k falls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O( bs(f)k).
Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f ⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
Joint complexity in the Decision Tree Model: We study the diversity of possible behaviors of the joint computational complexity of a collection f1, …, fk of Boolean functions over a shared input. We focus on the deterministic decision tree model, with depth as the complexity measure; in this model, we prove a result to the effect that the obvious constraints on joint computational complexity are essentially the only ones.
The proof uses an intriguing new type of cryptographic data structure called a mystery bin, which we construct using a polynomial separation between deterministic and unambiguous query complexity shown by Savický. We also pose a conjecture in the communication model which, if proved, would extend our result to that model. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened by UMI.)
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.