Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.9
URN: urn:nbn:de:0030-drops-124163
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12416/
Bassilakis, Andrew ; Drucker, Andrew ; Göös, Mika ; Hu, Lunjia ; Ma, Weiyun ; Tan, Li-Yang
The Power of Many Samples in Query Complexity
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bassilakis_et_al:LIPIcs:2020:12416,
author = {Andrew Bassilakis and Andrew Drucker and Mika G{\"o}{\"o}s and Lunjia Hu and Weiyun Ma and Li-Yang Tan},
title = {{The Power of Many Samples in Query Complexity}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {9:1--9:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12416},
URN = {urn:nbn:de:0030-drops-124163},
doi = {10.4230/LIPIcs.ICALP.2020.9},
annote = {Keywords: Query complexity, Composition theorems}
}
| Keywords: | Query complexity, Composition theorems | |
| Seminar: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 29.06.2020 |
