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

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

Download

Share

COinS