Sparse recovery, sampling, and dynamic data structures for graph problems
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.