Abstract
We establish two results regarding the query complexity of boundederror randomized algorithms.
Boundederror separation theorem. There exists a total function f : {0,1}^n > {0,1} whose epsilonerror 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 directsumtype 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 querytocommunication complexity lifting theorem of Göös, Pitassi, and Watson (2017), this also shows that there is a total function whose publiccoin 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).
BibTeX  Entry
@InProceedings{blais_et_al:LIPIcs:2019:10851,
author = {Eric Blais and Joshua Brody},
title = {{Optimal Separation and Strong Direct Sum for Randomized Query Complexity}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {29:129:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10851},
URN = {urn:nbn:de:0030drops108511},
doi = {10.4230/LIPIcs.CCC.2019.29},
annote = {Keywords: Decision trees, query complexity, communication complexity}
}
Keywords: 

Decision trees, query complexity, communication complexity 
Collection: 

34th Computational Complexity Conference (CCC 2019) 
Issue Date: 

2019 
Date of publication: 

16.07.2019 