CS Events Monthly View

Qualifying Exam

Multi-pass Semi-streaming Lower Bounds for Approximating Maximum Matching

 

Download as iCal file

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