Composition Theorem for Randomized Query Complexity

Introduction

A longstanding problem in Boolean function complexity is to determine how the complexity of a block composition relates to the complexities of its constituent functions. For total Boolean functions, tight composition theorems are known for deterministic query complexity and polynomial degree [11, 14, 16], as well as bounded-error quantum query complexity [9, 13]. Recently, [12] proved a composition theorem for approximate degree and showed that constant-factor multiplicative composition fails for exact quantum query complexity. In a latest development, [10] showed that constant-factor multiplicative composition fails for randomized query complexity even for total Boolean functions. Nevertheless, composition for randomized query complexity up to polylogarithmic factors remained open [3, 4, 6]. In this work, we resolve this question by establishing a composition lower bound with a logarithmic loss for all (possibly partial) Boolean functions.

Decision trees have been a fundamental model in computational complexity and have been studied extensively in the form of deterministic, randomized and quantum settings. Randomized query complexity of a Boolean function $f$ is the minimum worst-case number of queries required by a randomized decision tree to compute $f$. A long-standing open question has been

Recently, [10] showed that this lower bound does not hold true by giving a counter-example. However, the same bound with polylogarithmic factors remained open for total Boolean functions.

In the past, several papers have made progress towards answering whether composition of randomized query complexity holds by either showing lower bounds in terms of new related measures like noisy randomized query complexity, linearized randomized complexity, max-conflict complexity and randomized sabotage complexity or by showing the composition holds for some special class of families. [15] introduced a measure called randomized sabotage complexity, denoted by $\mathrm{RS}(f)$ and showed that $\mathrm{RS}(f) = O(\mathrm{R}(f))$ and $\mathrm{R}(f \circ g) = \Omega(\mathrm{R}(f)\mathrm{RS}(g))$. They also asked if $\mathrm{R}(f) = \Theta(\mathrm{RS}(f))$ for all total Boolean functions which would resolve the open conjecture of composition of randomized query complexity. Later, [7] introduced a measure called max-conflict complexity, denoted by $\overline{\chi}$ and showed that $\overline{\chi}(g) \in\Omega(\sqrt{\mathrm{R}_{1/3}(g)})$ for every partial Boolean function $g$ and $\mathrm{R}_{1/3}(f \circ g) = \Omega(\mathrm{R}_{4/9}(f)\overline{\chi}(g))$ and $\overline{\chi}(g) \geq\mathrm{RS}(g)$. They also proved a relation $\mathrm{R}_{1/3}(f \circ g) = \Omega(\mathrm{R}_{4/9}(f)\sqrt{\mathrm{R}_{1/3}(g)})$. [3] introduced noisy oracle model and a measure called noisy randomized query complexity, denoted by $\mathrm{noisyR}$ and showed that for all Boolean functions $f$, $\mathrm{noisyR}(f) \leq\mathrm{R}(f)$ and $\mathrm{R}(f \circ g) = \Omega(\mathrm{noisyR}(f)\mathrm{R}(g))$. They also gave a counter-example to $\mathrm{noisyR}(f) = \Omega(\mathrm{R}(f))$ and equivalently for $\mathrm{R}(f \circ g) = \Omega(\mathrm{R}(f)\mathrm{R}(g))$ using a partial function and thus refuted the constant-factor composition for partial Boolean functions. But the question remained open for the same bound with logarithmic factors. They conjectured that the following holds true

Thus, this conjecture is equivalent to the following question

Later, [6] showed that $\mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ for all Boolean functions with $\mathrm{R}(f) = \Theta(n)$. They also showed that if $\mathrm{R}$ composes with respect to an outer function, then $\mathrm{noisyR}$ also composes with respect to the same outer functions. Another paper [4] introduced a measure called linearized randomized complexity, denoted as LR, which is the largest possible measure satisfying $R(f \circ g) = \Omega(R(f)LR(g))$ for all partial Boolean functions $f,g$.

In this work, we show that bounded-error randomized query complexity composes multiplicatively with logarithmic factors. In particular, we establish that for every partial Boolean function, $\operatorname{noisyR}(f) = \widetilde{\Omega}(R(f))$. The main result is stated below:

AI Disclosure. We used ChatGPT 6 Astra to explore research directions, identify potential errors in arguments, simplify proof strategies, and improve the exposition. Our use of AI involved sustained back-and-forth discussions over several weeks. We explored numerous approaches drawn from the literature, including recent work, repeatedly refined our arguments, and pursued both proofs and potential counterexamples. Our initial attempts to establish a randomized composition result were consistently unsuccessful. Following the appearance of recent work on randomized composition [10], we asked ChatGPT 6 Astra to prove a weaker bound allowing a logarithmic loss. It succeeded in deriving this bound, leading to the randomized composition result presented here. The authors have rewritten the proof and take full responsibility for the mathematical content and final presentation.

Acknowledgment. We thank Srinivasan Arunachalam for helpful discussions.

Technical Overview

Noisy randomized model was introduced in [3] and they showed that for all partial Boolean functions $f$ and $g$,

The paper explicitly mentioned the following conjecture: for all (possibly partial) Boolean function $f$,

Therefore, to prove the bound in Question 2, it suffices to show that the above relation holds true. This paper heavily builds on the concepts used in [2, 3]. Let us first recap the noisy oracle model. Unlike the ordinary query model which reveals the queried bit exactly, in this noisy oracle model, a query with bias $\gamma$ returns the correct bit with probability $(1+\gamma)/2$ and costs $\gamma^{2}$. The measure $\operatorname{noisyR}$ captures the query complexity of such model. Let $\mathcal{A}$ be an arbitrary noisy randomized decision tree that computes the given function $f$ with error at most $1/3$ on every promised input $x \in D$ where $D$ is the domain of $f$. Let $T$ be the stopping time of $\mathcal{A}$. At step $t \le T$, $\mathcal{A}$ adaptively chooses a coordinate $i_t$ and a query strength $\gamma_t \in[0,1]$. Since the cost of the query is $\gamma_t^{2}$, the total noisy cost of the execution is $\sum_{t=1}^{T}\gamma_t^{2}$. The cost of a noisy randomized decision tree on an input $x$ is given by $\operatorname{cost}(\mathcal{A},x)=\mathbb{E}\left[\sum_{t=1}^{T}\gamma_t^{2}\right]$ and then the cost of $\mathcal{A}$ is $\max_{x\in D}\{\operatorname{cost}(\mathcal{A},x)\}$. Taking an infimum over the cost of all such noisy decision trees gives us $\operatorname{noisyR}(f)$. Thus, in order to prove the desired lower bound, we choose a hard distribution $\mu$ such that for every noisy decision tree $\mathcal{A}$,

This hard distribution $\mu$ is supplied by the minimax theorem of [2]. In particular, it is balanced, meaning $\Pr_{X\sim\mu}[f(X)=0]=\Pr_{X\sim\mu}[f(X)=1]=1/2$ and for every ordinary randomized algorithm $\mathcal{R}$ with terminal transcript $H$ and number of exact queries $Q$,

where $\beta$ is the posterior label bias

We will keep a track of an arbitrary noisy decision tree at every posterior state after each query using a function that we call “potential”, labeled as $W$. Building on top of the forecasting algorithm given in [2], we construct $W$ using auxiliary forecasting algorithms. Each such forecasting algorithm $\mathcal{B}$ gives a payoff which is the quantity below

Entropy regularization is a standard way to replace a hard maximum by a smooth log-sum-exp expression [8]. The potential is defined as the supremum of this expected payoff over all such auxiliary exact-query forecasting algorithms. After handling the case $R(f) \le2c$ separately, we particularly set this query charge term to be $\frac{2c}{R(f)}$ and the forecasting score to be the normalized Brier score. Note that this algorithm $\mathcal{B}$ is neither the same as an ordinary bounded-error randomized algorithm nor the noisy algorithm $\mathcal{A}$ that computes $f$ with an error $1/3$. This is just an adaptive algorithm that may stop querying and output the best forecast from the information available to it. This algorithm follows a dynamic programming framework (see [1]), expressed by a Bellman recurrence: it may stop and give the optimal value or perform additional queries and incur the associated cost. This potential, when evaluated at the algorithm’s posterior state, is initially small under the chosen hard distribution $\mu$. The expected increase on each noisy query is bounded by $O(\alpha\log(n+1))$ times noisy query’s cost and has a terminal expected value bounded below by a positive constant when the algorithm successfully terminates.

Let us look at the initial bound. Given a transcript, the best expected score is the squared posterior bias. The chosen hard distribution bounds this squared posterior bias of every auxiliary algorithm in terms of its expected number of queries averaged over all transcripts. In particular, it gives an upper bound of $c/R(f)$ times expected query count. Choose a sufficiently large query charge, that is, $\alpha= 2c/R(f)$ compared to this best expected score. Moreover, the entropy term is also sufficiently small. This makes the initial potential small.

Let us now bound the expected potential increase by one noisy query. When a noisy algorithm queries a bit, the observed answer re-weights the current posterior according to the query strength $\gamma$. Considering this re-weighted path, the expected increase in potential is a symmetric difference. For weak queries, meaning $\gamma\le1/2$, the first-order terms cancel and hence the bound on second derivative gives the dependence on $\gamma^2$. For stronger queries, that is $\gamma> 1/2$, convexity and exact-query charge suffice. If $\gamma_t$ is the strength of the query $t$ and $\mu_{t-1}$ is the current posterior before the query, we get the following bound

Summing the one query bounds and telescoping over the finite computation gives us the following total bound.

Let us now consider the terminal potential. Since the noisy randomized algorithm computes $f$ within an error of $1/3$, its terminal posterior has expected squared bias at least $1/9$. Since the potential is at least the best score obtained by stopping immediately, its terminal expectation is also at least $1/9$. If $\mu_T$ is the posterior when the noisy algorithm $\mathcal{A}$ terminates, then using the success probability of $\mathcal{A}$, we get,

This gives us a constant lower bound on the total potential increase. To achieve this, the expected total noisy cost has to be $\Omega(1/(\alpha\log(n+1)))$. Taking $\alpha= 2c/R(f)$ gives us the desired bound.

Now let us look at the construction of $W$. An auxiliary forecasting algorithm $B$ chooses a probability distribution $p_h$, depending on the history $h$, over the set of actions which is $\mathrm{ACT}=\{\ast,1,\ldots,n\}$. If it chooses $\ast$, then it stops, otherwise for $j\in[n]$, it queries $x_j$ exactly and continues. We also use a separate entropy term which is the entropy of this action distribution multiplied by a sufficiently small constant times $\alpha/\log(n+1)$. This keeps the entropy term at each decision small compared with the query charge. For the forecasting score, normalized Brier score $\operatorname{score}_{Br}(y,z)=1-4(y-z)^2$ is used.