[Theory] 4/16 Young Researcher Seminar Series: Vihan Shah, University of Waterloo

[Mary Marre via Theory]

*When:*        Wednesday, April 16, 2025 at* 11:00** am CT *


*Where:       *Talk will be given *live, in-person* at

                   TTIC, 6045 S. Kenwood Avenue

                   5th Floor, Room 530


*Virtually:*    *livestream via panopto
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=25343c36-0bba-4d24-b07e-b2ba017629ff>*



*Who: *         Vihan Shah, University of Waterloo



*Title*: Space Complexity of Minimum Cut Problems in Single-Pass Streams

*Abstract*: 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.

*Bio*: My research interest is in Theoretical Computer Science and
specifically in Streaming Algorithms. I have recently also worked on
Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy
working on Graph problems in these settings.

*Host: **Ali Vakilian* <vakilian at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250409/db1188b6/attachment-0001.html>