Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Abstract

We establish two results regarding the query complexity of bounded-error randomized algorithms. * Bounded-error separation theorem. There exists a total function $f:\{0,1{\}}^n\to \{0,1\}$ whose $\epsilon$-error randomized query complexity satisfies ${\overline{\mathrm{R}}}_{\epsilon }(f)=\Omega (\mathrm{R}(f)\cdot \log \frac{1}{\epsilon })$. * Strong direct sum theorem. For every function $f$ and every $k\ge 2$, the randomized query complexity of computing $k$ instances of $f$ simultaneously satisfies ${\overline{\mathrm{R}}}_{\epsilon }(f^k)=\Theta (k\cdot {\overline{\mathrm{R}}}_{\frac{\epsilon }{k}}(f))$. As a consequence of our two main results, we obtain an optimal superlinear direct-sum-type theorem for randomized query complexity: there exists a function $f$ for which $\mathrm{R}(f^k)=\Theta (k\log k\cdot \mathrm{R}(f))$. This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies ${\mathrm{R}}^{\mathrm{cc}}(f^k)=\Theta (k\log k\cdot {\mathrm{R}}^{\mathrm{cc}}(f))$, answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).

15 pages, 2 figures, CCC 2019

Cited by in corpus (1)

• When Is Amplification Necessary for Composition in Randomized Query Complexity?