2026-07-25T15:58:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10851 2024-03-06T10:46:52Z ddc:004 open_access

Optimal Separation and Strong Direct Sum for Randomized Query Complexity Blais, Eric Brody, Joshua Decision trees query complexity communication 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 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Blais and Joshua Brody 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.29 urn:nbn:de:0030-drops-108511 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode