## Document Type

Conference Proceeding

## Publication Date

2019

## Published In

34th Computational Complexity Conference

## Series Title

Leibniz International Proceedings In Informatics

## 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 -> {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).

## Keywords

Decision trees, query complexity, communication complexity}

## Published By

Schloss Dagstuhl: Leibniz-Zentrum Fuer Informatik

## Editor(s)

A. Shpilka

## Conference

34th Computational Complexity Conference

## Conference Dates

July 18-20, 2019

## Conference Location

New Brunswick, NJ

## Creative Commons License

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

## Recommended Citation

E. Blais and Joshua Brody.
(2019).
"Optimal Separation And Strong Direct Sum For Randomized Query Complexity".
*34th Computational Complexity Conference.*
Volume 137,

https://works.swarthmore.edu/fac-comp-sci/101