2026-07-26T04:38:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12416 2024-03-06T10:50:04Z ddc:004 open_access

The Power of Many Samples in Query Complexity Bassilakis, Andrew Drucker, Andrew Göös, Mika Hu, Lunjia Ma, Weiyun Tan, Li-Yang Query complexity Composition theorems The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew Bassilakis and Andrew Drucker and Mika Göös and Lunjia Hu and Weiyun Ma and Li-Yang Tan 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.9 urn:nbn:de:0030-drops-124163 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode