Optimal separation and strong direct sum for randomized query complexity
Optimal separation and strong direct sum for randomized query complexity
复制标题
针对随机查询复杂性的最佳分离和强直和
DOI：
10.4230/lipics.ccc.2019.29
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Joshua Brody
中科院分区：
文献类型：
--
作者：
Eric Blais;Joshua Brody
我们建立了有界越随机算法的查询复杂性的两个结果。强的总和定理。每个函数f和每个k≥2，f的随机查询复杂性简单地满足[方程]。结果，我们获得了随机查询复杂性的最佳超级直接和型定理：R（fk）= [等式]的功能f。查询到沟通复杂性提升理论的Göös，Pitassi和Watson（2017），这也表明，有一个全部功能，其公共COIN随机通信复杂性RCC（FK）= [等式]回答了费德，库希维茨，纳尔和尼桑（1995）的问题。
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 ∈-error randomized query complexity satisfies [EQUATION]. Strong direct sum theorem. For every function f and every k ≥ 2, the randomized query complexity of computing k instances of f simultaneously satisfies [EQUATION]. 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(fk) = [EQUATION]. 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 Rcc (fk) = [EQUATION], answering a question of Feder, Kushilevitz, Naor, and Nisan (1995).
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
BPP 的查询到通信提升
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas