Optimal Separation and Strong Direct Sum for Randomized Query Complexity

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\frac1\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"o"os, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies $$\mathrm{R}$^{$\mathrm{c}\mathrm{c}$} (f^k) = \Theta( k \log k \cdot $\mathrm{R}$^{$\mathrm{c}\mathrm{c}$}(f))$, answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).