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 both designing efficient sublinear graph simplifications methods, as well as researchers applying these methods, in order to explore new connections across sublinear algorithms.

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


Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop.

For additional information please visit: https://simons.berkeley.edu/participating-workshop.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Register Now