We give a strong direct sum theorem for computing $xor \circ g$. Specifically, we show that for every function g and every $k\geq 2$, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which $R(xor \circ g) = Θ(k \log(k)\cdot R(g))$, answering an open question from Ben-David et al.(arxiv:2006.10957v1).
We give a strong direct sum theorem for computing xor∘g. Specifically, we show that for every function g and every k≥2, the randomized query complexity of computing the xor of k instances of g satisfies R\eps(xor∘g)=Θ(kR\eps/k(g)). This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which R(xor∘g)=Θ(klog(k)⋅R(g)), answering an open question from Ben-David et al.(arxiv:2006.10957v1).
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).
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.
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f∘g)≪R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f∘g)=Ω(noisyR(f)⋅R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(⋅) satisfying R(f∘g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f∘gapmajn)/R(gapmajn)), where n is the input size of f and gapmajn is the n-gap majority function on n bits.
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.