Please note: This seminar will take place in DC 1304 and online.
Vihan Shah, Marie Curie Fellow in Theoretical Computer Science
University of Birmingham
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.
Bio: Vihan Shah is a Marie Curie Fellow at the University of Birmingham. He received his PhD in Computer Science from the University of Waterloo, and his bachelor’s and master’s degrees in Computer Science from Rutgers University. His research is in theoretical computer science, with a focus on streaming and sublinear algorithms for graph problems. He is broadly interested in understanding trade-offs between computational resources such as space, time, approximation, and adaptivity.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.