Optimal Separation And Strong Direct Sum For Randomized Query Complexity

Document Type

Conference Proceeding

Publication Date


Published In

34th Computational Complexity Conference


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 overline{R}_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 overline{R}_epsilon(f^k) = Theta(k * overline{R}_{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 Göös, 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).


Decision trees, query complexity, communication complexity}

Published By

Schloss Dagstuhl: Leibniz-Zentrum Fuer Informatik


A. Shpilka


34th Computational Complexity Conference

Conference Dates

July 18-20, 2019

Conference Location

New Brunswick, NJ

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.