
arXiv: 1908.01020
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 \to \{0,1\}$ whose $��$-error randomized query complexity satisfies $\overline{\mathrm{R}}_��(f) = ��( \mathrm{R}(f) \cdot \log\frac1��)$. * Strong direct sum theorem. For every function $f$ and every $k \ge 2$, the randomized query complexity of computing $k$ instances of $f$ simultaneously satisfies $\overline{\mathrm{R}}_��(f^k) = ��(k \cdot \overline{\mathrm{R}}_{\frac��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 $\mathrm{R}(f^k) = ��( k \log k \cdot \mathrm{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 $\mathrm{R}^{\mathrm{cc}} (f^k) = ��( k \log k \cdot \mathrm{R}^{\mathrm{cc}}(f))$, answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).
15 pages, 2 figures, CCC 2019
FOS: Computer and information sciences, Computer Sciences, Decision trees, Computational Complexity (cs.CC), communication complexity}, 004, Computer Science - Computational Complexity, query complexity, communication complexity, F.1.3, ddc: ddc:004
FOS: Computer and information sciences, Computer Sciences, Decision trees, Computational Complexity (cs.CC), communication complexity}, 004, Computer Science - Computational Complexity, query complexity, communication complexity, F.1.3, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
