• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Superlinear Lower Bounds for Multipass Graph Processing
【24h】

Superlinear Lower Bounds for Multipass Graph Processing

机译：多按摩图处理的超线性下限

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

摘要

We prove n^(1+Omega(1/p))/p^O(1) lower bounds for the space complexity of p-pass streaming algorithms solving the following problems on n-vertex graphs: * testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size), * testing if two specific vertices are at distance at most 2(p+1) in an undirected graph, * testing if there is a directed path from s to t for two specific vertices s and t in a directed graph. Prior to our result, it was known that these problems require Omega(n^2) space in one pass, but no n^(1+Omega(1)) lower bound was known for any p>=2. These streaming results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices reachable from a specific vertex in exactly p+1 steps intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem.
机译：我们证明了n ^（1 +ω（1 / p））/ p ^ o（1）P-PASS流算法的空间复杂度的下限解决了N-顶点图中的以下问题：*如果有一个无向图形的测试一个完美的匹配（这意味着用于计算最大匹配甚至是最大匹配尺寸的下限），*测试如果两个特定顶点处于最多2（p + 1）的距离，则为*测试是否存在在定向图中的两个特定顶点S和T的定向路径为两个特定顶点S和T。在我们之前，众所周知，这些问题需要在一次通过时需要ω（n ^ 2）空间，但是任何p＆＃x003e都知道下限N ^（1 + OMEGA（1））; = 2。这些流媒体结果从通信复杂性遵循的通信游戏，其中玩家在同一组顶点上持有两个图形的通信游戏。玩家的任务是找出从特定顶点到达的顶点的一组恰好P + 1步相交。只有当玩家被迫以特定的困难订单发言时，游戏才需要大量的通信。这使得诸如索引和指针追逐等通信问题的下限。除此之外，我们的攻击线需要证明经典指针追逐问题的决策版本的信息成本降低，以及用于此问题的几个实例的分离的直接和类型定理。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号