Fall 2018

Sublinear Algorithms and Nearest-Neighbor Search

Nov. 27Nov. 30, 2018

Add to Calendar


Robert Krauthgamer (Weizmann Institute; chair), Artur Czumaj (University of Warwick), Aarti Singh (Carnegie Mellon University), Rachel Ward (University of Texas at Austin)

Many applications require extreme computational efficiency, where the usage of resources, like runtime, storage, or data samples, is sublinear in the size of the input, and the workshop will cover different areas where this topic is studied, and explore connections between them. Specifically,  this topic received a lot of attention within Theoretical Computer Science, often motivated by advances in various application areas, and the workshop will review recent developments, such as algorithms for data streams, sketching, dimensionality reduction, graph sparsification, and property testing. In addition, the workshop will examine connections with linear and sublinear methods in Machine Learning, Statistics, Signal Processing and related areas, such as the well-known connections with compressed sensing, sparse recovery, and nearest-neighbor search. Some more recent connections are to online bandit problems and to distributed optimization, where constraints on algorithmic resources are just starting to be considered; such problems may be amenable to techniques from data-stream algorithms.

Invited Participants: 

Alex Andoni (Columbia University), Sepehr Assadi (University of Pennsylvania), Aditya Bhaskara (University of Utah), Vladimir Braverman (Johns Hopkins University), Clement Canonne (Stanford University), Constantine Caramanis (University of Texas at Austin), Moses Charikar (Stanford University), Sanjoy Dasgupta (UC San Diego), Anupam Gupta (Carnegie Mellon University), Piotr Indyk (MIT), Michael Kapralov (EPFL), Samory Kpotufe (Princeton University), Ravi Kumar (Google), Dustin Mixon (Ohio State University), Deanna Needell (University of California, Los Angeles), Rasmus Pagh (IT University of Copenhagen), Jeffrey Phillips (University of Utah), Eric Price (University of Texas at Austin), Sofya Raskhodnikova (Boston University), Ilya Razenshteyn (Microsoft Research), Ronitt Rubinfeld (MIT), Sujay Sanghavi (University of Texas at Austin), C. Seshadhri (UC Santa Cruz), Devavrat Shah (MIT), Aaron Sidford (Stanford University), Christian Sohler (Technische Universität Dortmund), Gregory Valiant (Stanford University), Soledad Villar (New York University)