UBC Theoretical Computer Science Theory Seminar: Vihan Shah
Topic
Minimum Cut in Single-Pass Streams
Speakers
Details
Computing the minimum cut is a fundamental problem in graph algorithms. In the streaming setting, exact computation requires essentially storing the entire stream, while the standard approach for a (1+eps)-approximation via cut sparsification uses roughly n/eps^2 space, which is optimal for cut sparsifiers.
In this talk, I will describe how we break this barrier for minimum cut, giving a streaming algorithm that reduces the space to roughly n/eps, together with a matching lower bound. The key idea is a new tool called for-each cut sparsifiers. Finally, I will discuss an elegant extension to dynamic streams, where edges may also be deleted.
Event Type
Scientific, Seminar
Date
November 20, 2026
Time
-
Location
Organizers
Sponsors