Title:
Sparse recovery, sampling, and dynamic data structures for graph problems
Abstract:
The work of Jowhari et al. 2010 showed how to use sparse recovery,
popular in the compressed sensing literature, to develop low-memory
schemes for sampling from a set being dynamically updated in a data
stream. Ahn, Guha, and McGregor in a sequence of two papers then
showed how to use this sampling primitive to solve a number of dynamic
graph problems using low memory, such as connectivity, and computing a
spanning forest, max matching, minimum spanning tree, and other such
graph problems. Much follow-up work has extended the AGM approach to
several other graph problems as well. In this talk, we discuss
optimality of these schemes for sampling and dynamic spanning forest
computation.
This talk is based on a couple of works, joint with subsets of Michael Kapralov, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh, and Huacheng Yu. |