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.

Further details about this workshop will be posted in due course.

Invited Participants: 

Alex Andoni (Columbia University), Sepehr Assadi (University of Pennsylvania), Vladimir Braverman (Johns Hopkins University), Constantine Caramanis (University of Texas at Austin), C. Comandur (UC Santa Cruz), Artur Czumaj (University of Warwick), Sanjoy Dasgupta (UC San Diego), Piotr Indyk (MIT), Michael Kapralov (Ecole Polytechnique Federale de Lausanne), Samory Kpotufe (Princeton University), Robi Krauthgamer (Weizmann Institute of Science), Deanna Needell (University of California, Los Angeles), Rasmus Pagh (IT University of Copenhagen), Eric Price (University of Texas at Austin), Ronitt Rubinfeld (Massachusetts Institute of Technology), Barna Saha (University of Massachusetts Amherst), Andrew Saxe (Oxford University), Devavrat Shah (Massachusetts Institute of Technology), Aarti Singh (Carnegie Mellon University), Christian Sohler (Technische Universität Dortmund), Suresh Venkatasubramanian (University of Utah), Soledad Villar (New York University), Rachel Ward (University of Texas at Austin), Ke Yi (Hong Kong University of Science & Technology)