2026-08-06T07:38:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20412 2024-07-15T12:26:45Z ddc:004 open_access

A Strong Direct Sum Theorem for Distributional Query Complexity Blanc, Guy Koch, Caleb Strassle, Carmen Tan, Li-Yang Query complexity direct product theorem hardcore theorem Consider the expected query complexity of computing the k-fold direct product f^{⊗ k} of a function f to error ε with respect to a distribution μ^k. One strategy is to sequentially compute each of the k copies to error ε/k with respect to μ 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 that holds for all functions in the standard query model 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^{⊗k} is likely to remain dense under arbitrary partitions of the input space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy Blanc and Caleb Koch and Carmen Strassle and Li-Yang Tan 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.16 urn:nbn:de:0030-drops-204123 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.16 eng https://creativecommons.org/licenses/by/4.0/legalcode