Direct Product Theorems for Randomized Query Complexity

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 $\hat{I}˜(n)$ times the "maximum distributional" query complexity of $f$ with success parameter ${\hat{I}}^3$. This result holds for all success parameters ${\hat{I}}^3$, even when ${\hat{I}}^3$ is very close to $1/2$ or to $1$. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for ${\hat{I}}^3$ bounded away from $\frac{1}{2}$ and $1$ as well as the strong direct sum theorem of Blais and Brody (2019) for ${\hat{I}}^3\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.

43 pages. In FOCS 2025