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) -> {0, 1} whose epsilon-error randomized query complexity satisfies (R) over bar epsilon(f) = Omega(R(f) . log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies (R) over bar epsilon(f(k)) = Theta(k . (R) over bar (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 R(f(k)) = Theta(k log k . R(f)). This answers an open question of Drucker (2012). Combining this result with the query-to-communication complexity lifting theorem of Goos, Pitassi, and Watson (2017), this also shows that there is a total function whose public-coin randomized communication complexity satisfies R-cc(f(k)) = Theta(k log k . R-cc(f)), answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).