Sepehr Assadi, Princeton University

Abstract

In the graph steaming model, the edges of an n-vertex graph are presented one by one in an arbitrary order and the algorithms can make one or a small number of sequential passes over this stream, while using a limited memory to process the graph. A graph streaming algorithm is considered efficient if it uses much smaller than O(n^2) memory (size of the input) and O(log n) passes over the input. It is well-known that allowing for multiple passes over the stream greatly enhances the capability of streaming algorithms and as a result multi-pass algorithms have been studied extensively in recent years. Despite this however, obtaining efficient streaming algorithms for many fundamental graph problems has remained elusive. This lack of progress has been further exacerbated by the fact that known techniques for streaming lower bounds are unable to prove any lower bounds beyond logarithmic number of passes except for a select few problems.

Abstract: In this talk, we present new tools for proving stronger multi-pass graph streaming lower bounds that break this logarithmic barrier. By using these new tools, we prove that a (small) polynomial number of passes are necessary for solving several fundamental graph problems including s-t maximum flow and s-t minimum cut that previously only admitted a logarithmic-pass lower bound. We also discuss the applicability of our techniques beyond streaming lower bounds: for instance, our techniques can also show that any algorithm for submodular function minimization needs almost quadratic number of queries to the function unless it has a polynomial degree of adaptivity.

Based on joint work with Yu Chen and Sanjeev Khanna.