We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0,1}^n -> {0,1} whose epsilon-error randomized query complexity satisfies overline{R}_epsilon(f) = Omega(R(f) * log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies overline{R}_epsilon(f^k) = Theta(k * overline{R}_{epsilon/k}(f)). As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function f for which R(f^k) = Theta(k log k * R(f)). This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies R^{cc}(f^k) = Theta(k log k * R^{cc}(f)), answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).
For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound
R(f∘g)=O(R(f)R(g)log(R(f)+1)) was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions
f and
g,
R(f∘g)=Ω(log(n+1)R(f)R(g)), where
n is the input size for
f.
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.
Consider the expected query complexity of computing the k-fold direct product
f⊗k of a function f to error
ε with respect to a distribution
μk . One strategy is to sequentially compute each of the k copies to error
ε/k with respect to
μ and apply the union bound. We prove a strong direct sum theorem showing that this naive strategy is essentially optimal. In particular, computing a direct product necessitates a blowup in both query complexity and error. Strong direct sum theorems contrast with results that only show a blowup in query complexity or error but not both. There has been a long line of such results for distributional query complexity, dating back to (Impagliazzo, Raz, Wigderson 1994) and (Nisan, Rudich, Saks 1994), but a strong direct sum theorem had been elusive. A key idea in our work is the first use of the Hardcore Theorem (Impagliazzo 1995) in the context of query complexity. We prove a new “resilience lemma" that accompanies it, showing that the hardcore of
f⊗k is likely to remain dense under arbitrary partitions of the input space.
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.
Let
Rϵ denote the randomized query complexity for error probability ε, and
R:=R1/3 . In this work, we investigate whether a perfect composition theorem
R(f∘gn)=Ω(R(f)⋅R(g)) holds for a relation
f⊆{0,1}n×S and a total inner function
g:{0,1}m→{0,1} . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that
R(f∘gn)=Ω(R(f)⋅RS(g)) , where
RS is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity
RS is asymptotically equivalent to
R for total Boolean functions. In this article, we show that
RS is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that
R is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called
Rprod , and proving it to be equivalent to
RS up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which
RS is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that
RS and
R are asymptotically equivalent for this function. We thus also show a polynomial separation between
R and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.