Consider the expected query complexity of computing the k-fold direct product <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$f^{\otimes k}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>f</mi> <mrow> <mo>⊗</mo> <mi>k</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> of a function f to error <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> with respect to a distribution <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mu ^k$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>μ</mi> <mi>k</mi> </msup> </math></EquationSource> </InlineEquation>. One strategy is to sequentially compute each of the k copies to error <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varepsilon /k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo stretchy="false">/</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> with respect to <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mu $</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$f^{\otimes k}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>f</mi> <mrow> <mo>⊗</mo> <mi>k</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> is likely to remain dense under arbitrary partitions of the input space.

A strong direct sum theorem for distributional query complexity

期刊论文
发表日期：

2026年5月5日

查看全文

Guy Blanc,
Caleb Koch,
Carmen Strassle,
Li-Yang Tan

摘要

Consider the expected query complexity of computing the k-fold direct product $f^{\otimes k}$ $f^{\otimes k}$ of a function f to error $\varepsilon $ $ε$ with respect to a distribution $\mu ^k$ $μ^{k}$ . One strategy is to sequentially compute each of the k copies to error $\varepsilon /k$ $ε / k$ with respect to $\mu $ $μ$ 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^{\otimes k}$ $f^{\otimes k}$ is likely to remain dense under arbitrary partitions of the input space.