CS Events

Qualifying Exam

Space Optimal Matching and Vertex Cover in dynamic streams

 

Download as iCal file

Friday, November 11, 2022, 02:30pm - 04:00pm

 

Speaker: Vihan Shah

Location : Zoom information: https://rutgers.zoom.us/j/91956380264?pwd=c1I0bFk3dkhwalVQMjlmZk1MY3ZrUT09 Meeting ID: 919 5638 0264 P

Committee

Prof. Aaron Bernstein

Prof. Jie Gao

Prof. Sepehr Assadi

Prof. Yipeng Huang

Event Type: Qualifying Exam

Abstract: We present algorithms for maximum matching and vertex cover in dynamic (insertion-deletions) streams with asymptotically optimal space complexity: for any n-vertex graph, our algorithms with high probability output an α-approximate matching in a single pass using O(n^2/α^3) bits of space and an α-approximate vertex cover using O(n^2/α^2) bits of space.A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to n^o(1) factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to polylog(n) factors [Dark-Konrad; CCC 2020]. [Dark-Konrad; CCC 2020] also gave upper and lower bounds for streaming vertex cover that were only a polylog(n) factor apart. Our upper bounds now match the DarkKonrad lower bounds up to O(1) factors, thus completing this research direction.Our approach consists of two main steps: we first (provably) identify a family of graphs, similar to the instances used in prior work to establish the lower bounds for this problem, as the only “hard” instances to focus on. These graphs include an induced subgraph which is both sparse and contains a large matching. We then design dynamic streaming algorithms for this family of graphs which is more efficient than prior work. The keys to this efficiency are novel sketching methods, which bypass the typical loss of polylog (n)-factors in space compared to standard L0-sampling primitives, and can be of independent interest in designing optimal algorithms for other streaming problems.