• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Overlays and Limited Memory Communication
【24h】

Overlays and Limited Memory Communication

机译：覆盖和内存通信有限

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models. We introduce the notion of rectangle overlay complexity of a function f. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in the communication matrix of f. Furthermore, we consider memory less and limited-memory communication models, originally introduced in Brody, Chen, Papakonstantinou, Song, and Sun with slightly different terminology. In these communication models there are two parameters of interest: The maximum message length s (which we think of as space) and the number of memory states w. Specifically, these are one-way protocols which proceed in rounds. In each round, Alice sends a message of at most s bits to Bob, receiving a message from Alice, Bob has to decide on the spot whether to output 0 or 1, or to continue the protocol. If he decides to continue, he immediately forgets Alice's message. In memory less protocols, no memory is transferred between different rounds (but Bob still has "space" to hold Alice's messages within each round). We can make Bob more powerful by giving him w memory states. He can change into a new state at the end of each round. We show that rectangle overlays completely characterize memory less protocols. Then, we go on to show several connections to the communication complexity polynomial hierarchy defined by Babai, Frankl and Simon in 1986. This hierarchy has recently regained attention because its connection to the algebrization barrier in complexity theory (Aaronson and Wigderson, 2009). We show that P^NP^cc is completely characterized by memory less protocols with polylog(n) space (maximum message length), and thus it admits a purely combinatorial characterization in terms of rectangle overlays. If Bob has 3 memory states and Alice sends messages of length polylog(n), they can compute every- level of Sigma_k in the communication complexity hierarchy (for constant k), and also every function in AC0. Furthermore, we show that with 5 memory states and messages of length polylog(n) they can compute exactly the functions in the communication class PSPACE^cc. This gives the first meaningful characterization of PSPACE^cc in terms of space, originally defined in Babai, Frankl, and Simon without any notion of space. We also study equivalences and separations between our limited memory communication model and branching programs, and relations to circuit classes.
机译：我们给在通信复杂性多项式的层次结构和电路的复杂性，以有限的内存通信模式等相关类新的刻画和下限。我们介绍的函数f的矩形覆盖复杂的概念。这是在f的通信矩阵的组合的矩形而言天然的组合复杂性量度。此外，我们认为更少的内存和内存有限的通信模型，最初在Brody，陈，PAPAKONSTANTINOU，宋，和Sun推出了略有不同的术语。在这些通信模型有感兴趣的两个参数：最大消息长度秒（这是我们所认为的空间）和内存状态W的数量。具体地讲，这些都是单向的协议，该协议继续在轮。在每一轮中，Alice发送的消息至多s比特给Bob，接收来自Alice的消息，Bob有当场决定是否输出0或1，或继续的协议。如果他决定继续下去，他马上忘记Alice的消息。在内存较小的协议，没有内存不同轮次之间转移（但鲍勃仍然有“空间”要保持每一轮中的爱丽丝的消息）。我们可以通过给他W¯¯内存鲍伯更加强大。他可以在每个回合结束时变成一个新的状态。我们表明，矩形覆盖完全表征更少的内存协议。然后，我们去上显示多个连接，通过八佰，弗兰克和西蒙1986年定义的通信复杂性多项式层次该层次最近重获关注，是因为它连接在复杂性理论（阿伦森和Wigderson，2009年）algebrization屏障。我们表明，P 1 NP ^ CC完全被polylog（n）的空间（最大消息长度）的特征在于记忆少协议，因此在承认矩形覆盖方面的纯的组合表征。如果Bob有3个存储器状态和Alice发送长度polylog（n）的消息，它们可以计算Sigma_k在通信复杂层次任何─电平（常数k），以及在每AC0功能。此外，我们显示，与5个存储器状态和长度polylog的消息（N），他们可以计算在所述通信类PSPACE ^ CC恰好功能。这就给出空间，原本在八佰伴，弗兰克和西蒙定义的术语PSPACE ^ CC的第一个有意义的特征没有任何空间的概念。我们还研究等价和我们有限的内存通信模型和分支程序之间的分离，以及关系电路类。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号