CS Events Monthly View
Qualifying ExamMulti-pass Semi-streaming Lower Bounds for Approximating Maximum Matching |
|
||
Wednesday, May 10, 2023, 01:30pm - 03:30pm |
|||
Abstract: In the semi-streaming model for processing graphs, the edges of n-vertex input graphs are presented to the algorithms in a stream and the algorithms are allowed to make one or more passes over this stream and use ~O(n) space to compute the answer. In recent years, semi-streaming algorithms have been at the forefront of theoretical research on processing massive graphs.
In this talk, I will overview my research in proving lower bounds for graph streaming. We will particularly focus on the maximum matching problem, which is one of the most studied problems in this model. We prove that any 1-eps multiplicative approximation of maximum matching (or even just its size) requires Omega(log(1/eps)) passes, under a natural combinatorial hypothesis that moderately dense Ruzsa-Szemeredi graphs do exist.
Speaker: Janani Sundaresan
Location : CoRE 301
Committee:
Professor Sepehr Assadi (Advisor)
Professor Aaron Bernstein
Professor Mike Saks
Professor Yongfeng Zhang
Event Type: Qualifying Exam
Abstract: See above
Organization:
Rutgers University
School of Arts & Sciences
Department of Computer Science
Contact Professor Sepehr Assadi