Fall 2023

Sketching and Algorithm Design

Monday, Oct 9, 2023 to Friday, Oct 13, 2023 

Add to Calendar


Jelani Nelson (UC Berkeley; chair), Michael Kapralov (Ecole Polytechnique Fédérale de Lausanne), Sepideh Mahabadi (Massachusetts Institute of Technology), Andrew McGregor (University of Massachusetts), David Woodruff (Carnegie Mellon University)

A sketch of a dataset is a compressed representation of it that still supports answering some set of interesting queries. Sketching has numerous applications including, finding applications to streaming algorithm design, faster dynamic data structures (with some applications to offline algorithms, especially in optimization), distributed algorithms and optimization, and federated learning. This workshop will focus on recent advances in sketching and various such applications. Talks will cover both advances and open problems in the specific area of sketching as well as improvements in other areas of algorithm design that have leveraged sketching results as a key routine. 

Specific topics to cover include sublinear memory data structures for dynamic graphs, sketching for machine learning, robust sketching to adaptive adversaries, and the interplay between differential privacy and related models with sketching.

To contact the organizers about this workshop, please complete this form.

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