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 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 [at] berkeley.edu with as much advance notice as possible.
Chairs/Organizers
Invited Participants
Soheil Behnezhad (Northeastern University), Yu Chen (EPFL), Mahsa Derakhshan (UC Berkeley), Elena Grigorescu (Purdue), Sanjeev Khanna (University of Pennsylvania), 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 Birmingham), 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), Santhoshini Velusamy (Toyota Technological Institute at Chicago), Nicole Wein (University of Michigan), Yuval Wigderson (ETH Zurich), Samson Zhou (Texas A&M University)