The Power of Many Samples in Query Complexity

Andrew Bassilakis, Andrew Drucker, Mika Göös +3

The randomized query complexity $R(f)$ of a boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to dis…