Polynomial pass lower bounds for graph streaming algorithms
Polynomial pass lower bounds for graph streaming algorithms
复制标题
DOI：
10.1145/3313276.3316361
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Yu Chen;S. Khanna
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Yu Chen;S. Khanna
我们提出了新的下界，表明多项式数量的通行证是必要的，解决一些基本的图形问题的流模型的计算。例如，我们证明了任何在n顶点无向图中找到加权最小s-t割的流算法都需要n2−o（1）空间，除非它使nΩ（1）通过流。为了证明我们的下限，我们引入并分析了一个新的四人通信问题，我们称之为隐藏指针追逐问题。这是一个标准的指针追逐问题的精神与关键的区别，在这个问题中的指针是隐藏的球员，找到他们中的每一个需要解决另一个通信问题，即集合相交问题。我们的下界图的问题，然后获得减少隐藏指针追逐问题。我们的隐藏指针追踪问题看起来足够灵活，可以找到其他应用程序，因此本身就很有趣。为了展示这一点，我们进一步提出了一个有趣的应用程序，这个问题超出流算法。使用隐藏指针追踪的约简，我们证明了任何子模函数最小化的算法都需要对函数进行n2−o（1）值查询，除非它具有多项式阶的自适应性。
We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum s-t cut in an n-vertex undirected graph requires n2−o(1) space unless it makes nΩ(1) passes over the stream. To prove our lower bounds, we introduce and analyze a new four-player communication problem that we refer to as the hidden-pointer chasing problem. This is a problem in spirit of the standard pointer chasing problem with the key difference that the pointers in this problem are hidden to players and finding each one of them requires solving another communication problem, namely the set intersection problem. Our lower bounds for graph problems are then obtained by reductions from the hidden-pointer chasing problem. Our hidden-pointer chasing problem appears flexible enough to find other applications and is therefore interesting in its own right. To showcase this, we further present an interesting application of this problem beyond streaming algorithms. Using a reduction from hidden-pointer chasing, we prove that any algorithm for submodular function minimization needs to make n2−o(1) value queries to the function unless it has a polynomial degree of adaptivity.