A Strong Direct Sum Theorem for Distributional Query Complexity
<|reference_start|>A Strong Direct Sum Theorem for Distributional Query Complexity: Consider the expected query complexity of computing the $k$-fold direct product $f^{\otimes k}$ of a function $f$ to error $\varepsilon$ with respect to a distribution $\mu^k$. One strategy is to sequentially compute each of the $k$ copies to error $\varepsilon/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}$ is likely to remain dense under arbitrary partitions of the input space.<|reference_end|>
@article{blanc2024a,
    title={A Strong Direct Sum Theorem for Distributional Query Complexity},
    author={Guy Blanc and Caleb Koch and Carmen Strassle and Li-Yang Tan},
    journal={arXiv preprint arXiv:2405.16340},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.16340},
    primaryClass={cs.CC}
}