The Power of Many Samples in Query Complexity
2020Β
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI