[Theory] TODAY: 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>*


On Tue, Apr 15, 2025 at 2:44 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Wed, Apr 9, 2025 at 7:28 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20250416/31dc334d/attachment-0001.html>