Sublinear Algorithms and Nearest-Neighbor Search
2018-11-27..2018-11-30
Berkeley, United States
[Extroverted Sublinear Algorithms 2024, Information Theory, Learning and Big Data (Simons Institute, 2015), Sketching and Algorithm Design 2023, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Randomized Numerical Linear Algebra and Applications 2018, Optimization and Algorithm Design 2023]
who it's for
sublinear algorithms researchers, machine learning researchers, search and nearest-neighbor engineers, streaming and sketching engineers, privacy and distribution-testing engineers, data scientists building large-scale clustering
topics
learned frequency sketches; Count-Min and CountSketch techniques; adaptive sparse recovery bounds; local-access random graph generators; importance sampling via locality-sensitive hashing; local differential privacy for testing; sublinear k-means certification via SDP; palette sparsification for vertex coloring; fast nearest-neighbor prediction methods; efficient k-nearest neighbor reductions; robust high-dimensional sparse regression; coresets for scalable spatial scan statistics
| title | author | length |
|---|---|---|
| Learning-Augmented Sketches for Frequency Estimation | Piotr Indyk | 46m |
Augments hashing-based frequency sketches with a learned binary oracle (RNN and decision-tree attempts) that flags heavy items after training on a prefix, then… | ||
| Adaptive Sparse Recovery with Limited Adaptivity | Eric Price | 42m |
Shows nearly tight measurement bounds for r-round adaptive sparse recovery: for constant rounds r the paper proves lower bounds of about Ω(k log^{1/r} n) and… | ||
| Universal Sketches | Vladimir Braverman | 39m |
Claim: a single compact sketch approximates an entire family of functions (sums g(v_i), many symmetric norms) rather than one per query. Construction uses a… | ||
| Erasures vs. Errors in Local Decoding and Property Testing | Sofya Raskhodnikova | 44m |
Constructs a specific n-bit property that is alpha-erasure-resilient testable with constant queries yet requires polynomial (indeed near-linear) queries for… | ||
| Testing and Learning Distributions Under Local Information Constraints | Clément Canonne | 45m |
Study uses the simultaneous referee model with n players each getting one sample and limited by a family of channels W. Exact claims: centralized sample needs… | ||
| Sublinear Time Local-Access Random Generators | Ronitt Rubinfeld | 41m |
Generates huge random graphs on the fly and answers vertex-pair, next-neighbor, all-neighbor and random-neighbor queries while spending polylogarithmic time… | ||
| Importance Sampling in High Dimensions via Hashing | Moses Charikar | 01h 02m |
Shows a concrete technique: turn locality‑sensitive hashing into an importance sampler so kernel‑sum estimation gets query time ~1/√μ (vs 1/μ for uniform… | ||
| Labeling a Data Set Using Sublinearly Many Queries | Sanjoy Dasgupta | 58m |
Classic uncertainty heuristics are provably inconsistent — they can converge to the wrong classifier even with infinite labels. The alternative active… | ||
| An Optimal Space Lower Bound for Approximating MAX-CUT | Michael Kapralov | 45m |
Shows that in the single-pass streaming model any algorithm that beats a trivial factor-2 for MAX-CUT (specifically any 2−ε approximation for constant ε>0)… | ||
| Sublinear Algorithms for (Delta + 1) Vertex Coloring | Sepehr Assadi | 42m |
Claim: sampling O(log n) random colors per vertex (a palette sparsification) suffices, with high probability, to retain a Delta+1 coloring. Tools: use the HSS… | ||
| Monte Carlo Approximation Certificates for K-Means Clustering | Dustin Mixon | 40m |
Shows that a semi-definite relaxation of k‑means yields a verifiable certificate: compute an SDP solution, derive a dual certificate (reduced to an eigenvalue… | ||
| Certified Sub-Linear Lower Bounds for K-Means Clustering | Soledad Villar | 28m |
Claims a sub-linear certifier for k‑means that computes probabilistic lower bounds by solving an SDP on random subsets of the data, so total work depends on… | ||
| High Dimensional Robust Sparse Regression | Constantine Caramanis | 45m |
Shows that under i.i.d. Gaussian covariates and a k-sparse coefficient, a constant fraction epsilon of adversarial X and y outliers can be tolerated by… | ||
| Online Algorithms for Low Rank Approximation | Aditya Bhaskara | 44m |
Proposes an online algorithm that produces a low‑dimensional embedding achieving a one‑plus‑epsilon approximation for PCA under two assumptions: a rough… | ||
| Fast NN Prediction with No Statistical Tradeoff | Samory Kpotufe | 40m |
Claims that K nearest-neighbor accuracy (with optimal K ~ sqrt(n)) is attainable in O(log n) prediction time by reducing the dataset via quantization or… | ||
| Spectral Partitioning for Metrics (And NNs Too) | Alex Andoni | 46m |
Gives a concrete parameter, the cutting modulus, and proves it controls approximate nearest‑neighbor complexity: for any norm on R^d there is a cell‑probe data… | ||
| Holder Homeomorphisms and Approximate Nearest Neighbors | Ilya Razenshteyn | 48m |
New algorithms give time‑efficient ANN for arbitrary norms in R^D with subpolynomial approximation (exp((log D)^{2/3})) using polynomial space and… | ||
| Efficient Reductions for k-Nearest Neighbor Search | Rasmus Pagh | 40m |
Proposes a practical stopping rule called confirmation sampling that queries multiple LSH-style structures until the current best point appears T+1 times… | ||
| When Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors | C. Seshadhri | 42m |
A MapReduce-style algorithm (WIMP) combines wedge sampling (Cohen–Lewis) with SimHash sketches to approximate all pairs with cosine similarity ≥ τ while… | ||
| Nearly Linear Time Algorithms for Solving Inverse Symmetric M-Matrices | Aaron Sidford | 51m |
Provides algorithms that recover and solve three hard cases—perturbed Laplacians, Laplacian pseudoinverses, and inverse symmetric M-matrices—by producing a… | ||
| Scalable Spatial Scan Statistics with Coresets | Jeff Phillips | 41m |
Presents a practical pipeline that builds small geometric coresets to scan millions of geo-located points: construct an epsilon-sample (often ~2–3k points) and… | ||
| nothing matches | ||