The Power of Many Samples in Query Complexity

2020/02/25 by Bassilakis, Andrew, Drucker, Andrew, Göös, Mika +3
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2002.10654

Abstract

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

Related

• Randomised Composition and Small-Bias Minimax
• Towards Better Separation between Deterministic and Randomized Query Complexity
• Approximating the Influence of a monotone Boolean function in\n O(\√(n)) query complexity
• Direct Product Theorems for Randomized Query Complexity
• Randomized query composition and product distributions