Workshops

Fall 2018

Sublinear Algorithms and Nearest-Neighbor Search

Nov 27, 2018 to Nov 30, 2018

Return to event »

Click on the titles of individual talks for abstract, slides and archived video.

Tuesday, November 27th, 2018
9:00 am–9:20 am		Coffee and Check-In
9:20 am–9:30 am		Opening Remarks
9:30 am–10:10 am		Learning-Augmented Sketches for Frequency Estimation Piotr Indyk (Massachusetts Institute of Technology)
10:20 am–11:00 am		Adaptive Sparse Recovery with Limited Adaptivity Eric Price (University of Texas at Austin)
11:10 am–11:30 am		Break
11:30 am–12:10 pm		Universal Sketches Vladimir Braverman (Johns Hopkins University)
12:20 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		Approximating the Cost of a Metric K-Nearest Neighbor Graph in Sublinear Time Christian Sohler (Technische Universität Dortmund and Google Switzerland)
2:50 pm–3:30 pm		Testing and Learning Distributions Under Local Information Constraints Clement Canonne (Stanford University)
3:40 pm–4:00 pm		Break
4:00 pm–4:40 pm		Erasures vs. Errors in Local Decoding and Property Testing Sofya Raskhodnikova (Boston University)
4:50 pm–5:30 pm		Sublinear Time Local-Access Random Generators Ronitt Rubinfeld (Massachusetts Institute of Technology)
5:40 pm		Reception

Wednesday, November 28th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Importance Sampling in High Dimensions via Hashing Moses Charikar (Stanford University)
10:40 am–11:00 am		Break
11:00 am–12:00 pm		Labeling a Data Set Using Sublinearly Many Queries Sanjoy Dasgupta (UC San Diego)
12:10 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		An Optimal Space Lower Bound for Approximating MAX-CUT Michael Kapralov (Ecole Polytechnique Federale de Lausanne)
2:50 pm–3:30 pm		Sublinear Algorithms for (Delta + 1) Vertex Coloring Sepehr Assadi (University of Pennsylvania)
3:40 pm–4:00 pm		Break
4:00 pm–4:40 pm		Monte Carlo Approximation Certificates for K-Means Clustering Dustin Mixon (Ohio State University)
4:50 pm–5:30 pm		Certified Sub-Linear Lower Bounds for K-Means Clustering Soledad Villar (New York University)

Thursday, November 29th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		High Dimensional Robust Sparse Regression Constantine Caramanis (University of Texas at Austin)
10:20 am–11:00 am		Online Algorithms for Low Rank Approximation Aditya Bhaskara (University of Utah)
11:10 am–11:30 am		Break
11:30 am–12:10 pm		Fast NN Prediction with No Statistical Tradeoff Samory Kpotufe (Princeton University)
12:20 pm–2:00 pm		Lunch
2:00 pm–2:40 pm		Spectral Partitioning for Metrics (And NNs Too) Alex Andoni (Columbia University)
2:50 pm–3:30 pm		Holder Homeomorphisms and Approximate Nearest Neighbors Ilya Razenshteyn (Microsoft Research)
3:40 pm–4:00 pm		Break
4:00 pm–4:40 pm		Efficient Reductions for k-Nearest Neighbor Search Rasmus Pagh (IT University of Copenhagen)

Friday, November 30th, 2018
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:10 am		When Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors C. Seshadhri (UC Santa Cruz)
10:20 am–11:00 am		Efficient Structured Matrix Recovery and Nearly Linear Time Algorithms for Solving Inverse Symmetric M-Matrices Aaron Sidford (Stanford University)
11:10 am–11:30 am		Break
11:30 am–12:10 pm		Scalable Spatial Scan Statistics with Coresets Jeff Phillips (University of Utah)
12:20 pm–1:30 pm		Lunch at the Simons Institute
1:30 pm–3:00 pm		Panel: Can Theory and Machine Learning Meet?
3:10 pm–3:30 pm		Break
3:30 pm–5:00 pm		Rump Session (Open Problems + Short Talks)