Direct Product Theorems for Randomized Query Complexity
Authors
Shalev Ben-David
Eric Blais
Abstract
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 $\frac12$ and $1$ as well as the strong direct sum theorem of Blais and Brody (2019) for $γ\approx 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 $f^n$ 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.
