2025/12/09 by Ben-David, Shalev, Blais, Eric
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · doi:10.48550/arxiv.2512.08268
openalex publication_date 2025/12/09 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
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 γ≈ 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.