Theory Lunch Seminar - Richard Peng

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
RICHARD PENG, Associate Professor, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~yangp/

This talk discusses the dynamic matching problem, which seeks to maintain a large matching / small vertex cover in a graph undergoing edge insertions/deletions. It covers recent progresses on maintaining $(1 + \epsilon)$-approximations in unweighted bipartite graphs. The two main topics of focus are sparsification and MWU based reductions to vertex-dynamic cases with larger errors, and connections with Rusza-Szemeredi graphs and the online matrix-vector multiplication conjecture in such settings.

Event Website:
https://www.cs.cmu.edu/~theorylunch/

Add event to Google
Add event to iCal