About

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.

Chairs/Organizers
Invited Participants

Mahsa Derakhshan (UC Berkeley), Elena Grigorescu (Purdue), Christian Konrad (University of Bristol, UK), Akash Kumar (IIT Bombay), Hung Le (University of Massachusetts Amherst), Quanquan Liu (Simons Institute), Andrew McGregor (University of Massachusetts Amherst), Sagnik Mukhopadhyay (University of Sheffield), Aaron Putterman (Harvard University), Sayantan Sen (Centre for Quantum Technologies, National University of Singapore), Asaf Shapira (Tel-Aviv University), Madhu Sudan (Harvard University), Janani Sundaresan (University of Waterloo), Virginia Vassilevska Williams (Massachusetts Institute of Technology), Nicole Wein (University of Michigan), Yuval Wigderson (ETH Zurich)

Register

Registration is required for in-person attendance, access to the livestream, and early access to the recording. Space may be limited, and you are advised to register early. 

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