The Landscape of Communication Complexity Classes
The Landscape of Communication Complexity Classes
复制标题
通信复杂性类的概况
DOI：
10.1007/s00037-018-0166-6
复制
发表时间：
2018
影响因子：
1.4
通讯作者：
Watson, Thomas
中科院分区：
文献类型：
--
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
我们证明了几个结果，连同以前的工作，提供了一个几乎完整的图片之间的经典通信复杂性类之间的关系，证明下界对类没有明确的下界已经知道。我们的文章也是对结构通信复杂性的最新研究，在我们的新结果中，我们证明了Merlin-Arthur证明系统不能被具有一个随机性的零侧错误随机协议模拟。在这里，类具有这样的性质，即以最轻微的方式推广它将使它包含，众所周知，要证明任何明确的下界都是开放的。我们还证明了，其中的类的规范完全问题是集不相交的变体，是的实例是唯一相交。我们还证明了，其中是两个集合的差类。最后，我们探讨了一个有趣的开放问题：秩1矩阵固有的通信复杂性比矩形更强大？我们证明了一个新的分离问题，它揭示了这个问题并加强了一些以前已知的分离。
We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes betweenand, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on the state of structural communication complexity.Among our new results we show that, that is, Merlin–Arthur proof systems cannot be simulated by zero-sided error randomized protocols with onequery. Here the classhas the property that generalizing it in the slightest ways would make it contain, for which it is notoriously open to prove any explicit lower bounds. We also prove that, whereis the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that, whereis the class of differences of twosets. Finally, we explore an intriguing open issue: Are rank-1 matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerningthat sheds light on this issue and strengthens some previously known separations.
登录
查看更多内容
关于 Oracle 访问一个查询的零错误算法
影响因子：
1
作者：
Jin;Venkatesan T. Chakaravarthy
通讯作者：
Venkatesan T. Chakaravarthy
关于唯一可满足性和随机归约的阈值行为
DOI：
--
发表时间：
1995
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
Richard Chang;Jim Kadin;P. Rohatgi
通讯作者：
P. Rohatgi
矩形是非负 Juntas
DOI：
10.1145/2746539.2746596
发表时间：
2015
期刊：
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Mika Göös;Shachar Lovett;Raghu Meka;Thomas Watson;David Zuckerman
通讯作者：
David Zuckerman
DOI：
10.1016/0022-0000(86)90046-2
发表时间：
1986-08
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
R. Paturi;Janos Simon
通讯作者：
R. Paturi;Janos Simon
DOI：
--
发表时间：
1993
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
Yenjo Han;L. Hemaspaandra;T. Thierauf
通讯作者：
T. Thierauf