Direct Product Theorems for Randomized Query Complexity

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

Authors

• Shalev Ben-David
• Eric Blais

Keywords

• Computer science
• Boolean functions
• Complexity theory
• Decoding
• Direct Product
• Query Complexity
• Complex Functions
• Complexity Measures
• Direct Questions
• Boolean Function
• Random Variables
• Upper Bound
• Loss Of Generality
• Decision Tree
• Scoring Function
• Average Cost
• Average Probability
• Product Distribution
• Convex Function
• Binary Entropy
• Jensen’s Inequality
• Cost Of Algorithm
• Real Input
• Worst-case Complexity
• Input Bits
• Expected Time