Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-027 | 26th February 2020 20:54

The Power of Many Samples in Query Complexity

RSS-Feed




TR20-027
Authors: Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
Publication: 26th February 2020 21:45
Downloads: 904
Keywords: 


Abstract:

The randomized query complexity R(f) of a boolean function f\colon\{0,1\}^n\to\{0,1\} is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution D_0 over 0-inputs from a distribution D_1 over 1-inputs, maximized over all pairs (D_0,D_1). We ask: Does this task become easier if we allow query access to infinitely many samples from either D_0 or D_1? We show the answer is no: There exists a hard pair (D_0,D_1) such that distinguishing D_0^\infty from D_1^\infty requires \Theta(R(f)) many queries. As an application, we show that for any composed function f\circ g we have R(f\circ g) \geq \Omega(\mathrm{fbs}(f)R(g)) where \mathrm{fbs} denotes fractional block sensitivity.



ISSN 1433-8092 | Imprint