PhD Seminar • Algorithms and Complexity • Space Complexity of Minimum Cut Problems in Single-Pass Streams

Please note: This PhD seminar will take place in DC 1304 and online.

Vihan Shah, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Sepehr Assadi

We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. Since finding the exact minimum cut essentially requires you to store the entire stream, we study the (1+eps)-approximate minimum cut problem. An upper bound for streaming (1+eps)-approximate minimum cut easily follows from streaming (1+eps) cut sparsification which is a very well-studied problem. It has an upper bound using O(n polylog n / eps^2) space [AG09] and a lower bound of Omega(n/eps^2) bits [CKST19]. This immediately provides an upper bound of O(n polylog n / eps^2) bits for streaming (1+eps)-approximate minimum cut, but the lower bound does not carry over. The best lower bound for (1+eps)-approximate minimum cut is Omega(n log 1/eps) bits [AG09]. This raises the fundamental question, what is the streaming space complexity of (1+eps)-approximate minimum cut?

In our paper we resolve this question up to polylogarithmic factors. Additionally, we explore the random-order streaming model, a relaxation of the adversarial streaming model, and demonstrate that significantly better bounds can be achieved in this setting.

To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.