Sublinear Graph Simplification

The concept of simplifying a graph is ubiquitous in numerous areas of research. Some well-established examples are graph sparsifiers and spanners used in the design of fast polynomial-time algorithms, partition oracles used in the design of sublinear time algorithms for sparse graphs, and Szemeredi’s regularity lemma (and its many variants) used in extremal graph theory and in testing dense graphs. More recent examples are the use of random walks to design efficient spectral partitioning algorithms, the study of palette sparsifiers, and local sparsifiers that maintain connectivity properties. Such methods have also been instrumental in the study of fine-grained complexity questions.

This workshop will bring together researchers working on designing efficient sublinear graph simplification methods, as well as researchers applying these methods, to explore new connections across sublinear algorithms.

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.