Sublinear Algorithms and Nearest-Neighbor Search
Organizers:
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.
Alex Andoni (Columbia University), Ery Arias-Castro (UC San Diego), Sepehr Assadi (University of Pennsylvania), Peter Bartlett (UC Berkeley), Shai Ben-David (University of Waterloo), 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), Yeshwanth Cherapanamjeri (UC Berkeley), Ken Clarkson (IBM Almaden), Sanjoy Dasgupta (UC San Diego), Ilias Diakonikolas (University of Southern California), Jelena Diakonikolas (Boston University), Simon Du (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), Wooseok Ha (UC Berkeley), Piotr Indyk (MIT), Adel Javanmard (USC), Rajesh Jayaram (Carnegie Mellon University), T.S. Jayram (IBM Almaden Research), Brendan Juba (Washington University in St. Louis), John Kallaugher (University of Texas at Austin), Michael Kapralov (Ecole Polytechnique Federale de Lausanne (EPFL)), Samory Kpotufe (Princeton University), Ravi Kumar (Google), Jerry Li (Massachusetts Institute of Technology), Michael Mahoney (International Computer Science Institute and UC Berkeley), Dustin Mixon (Ohio State University), Marco Mondelli (Stanford University), Rasmus Pagh (IT University of Copenhagen), Sourabh Palande (University of Utah), Eric Price (University of Texas at Austin), Sofya Raskhodnikova (Boston University), Ilya Razenshteyn (Microsoft Research), Ronitt Rubinfeld (Massachusetts Institute of Technology), Hamed Saleh (University of Maryland), C. Seshadhri (UC Santa Cruz), Fei Shi (Carnegie Mellon University), Aaron Sidford (Stanford University), Christian Sohler (Technische Universität Dortmund), Zhao Song (University of Texas at Austin), Yan Shuo Tan (University of Michigan), Soledad Villar (New York University), Anastasia Voloshinov (USC), Bei Wang (University of Utah), David Woodruff (Carnegie Mellon University), Shirley Wu (University of Texas at Austin)
