Extroverted Sublinear Algorithms 2024
2024-06-17..2024-06-21
Berkeley, United States
[Sublinear Algorithms and Nearest-Neighbor Search, Learning, Algorithm Design and Beyond Worst-Case Analysis, Information Theory, Learning and Big Data (Simons Institute, 2015), Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013), Dynamic Graphs and Algorithm Design (Simons Institute, 2023)]
who it's for
algorithms researchers, machine learning researchers, privacy engineers, streaming systems engineers, data engineers for similarity search, parallel and distributed systems engineers
topics
approximate counting bounds; locally private histogram protocols; coin-weighing graph queries; deterministic quantile sketches; earth mover's distance ANN; MPC Euclidean MST approximation; private similarity summaries; efficiency for large models; near-linear long-context attention; randomized least-squares for tensor decomposition; streaming connectivity augmentation; sublinear graph sampling methods
| title | author | length |
|---|---|---|
| New upper and lower bounds on approximate counting | Jelani Nelson | 48m |
Proves tight upper and lower bounds for Morris-style approximate counters, replacing the old log 1/δ failure-term by a log-log 1/δ dependence and showing this… | ||
| Locally Private Histograms in All Privacy Regimes | Clément Canonne | 26m |
Shows that the standard bitwise randomized-response protocol RAPPOR already attains much better accuracy in the low-privacy (large ε) regime once analyzed with… | ||
| Shaving logs by weighing coins | Deeparnab Chakrabarty | 39m |
Claims an order-n expected cut-query algorithm to find a spanning forest (shaving the standard n log n), using coin-weighing / Lindström–Cantor–Mills… | ||
| Optimal Quantile Estimation for Streams | Mihir Singhal | 38m |
Describes a deterministic quantile sketch that achieves deterministic O(1/ε) words space, matching a new lower bound. Builds on Q-digest trees but processes… | ||
| O(log s)-Approximate Nearest Neighbor Search for the Earth Mover’s Distance | Rajesh Jayaram | 37m |
Presents the first improvement in approximation for ANN under Earth Mover’s Distance in over a decade, reducing prior O(log^2 s) to Õ(log s) while keeping… | ||
| Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree | Peilin Zhong | 28m |
Produces a constant-factor approximation to the Euclidean MST on n points in Rd using a new MPC algorithm that runs in O~(loglog n) rounds with near-linear… | ||
| Efficiently Computing Similarities to Private Datasets | Sandeep Silwal | 30m |
Proposes a private summary that answers similarity queries (sum of f(x,y)) with small additive error that does not grow with n by reducing L1 to per-coordinate… | ||
| ML Efficiency for Large Models: From Data Efficiency to Faster Transformers | Vahab Mirrokni | 36m |
Describes concrete methods and measured wins: sensitivity sampling combines k‑means clustering with importance scores to match full‑data gradients and guides… | ||
| Sub-Linear Algorithms meets Large Language Models | Anshumali Shrivastava | 41m |
Argues that inference computes mostly zeros — measured 95% zeros in attention for a 175B model — and proposes dynamic per-input parameter selection using… | ||
| Randomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp... | Tamara Kolda | 33m |
Randomized approximate leverage-score sampling uses the Khatri–Rao structure of tensor ALS least-squares to avoid forming the giant design matrix, sampling… | ||
| Long-context Attention in Near-Linear Time | David P. Woodruff | 41m |
HyperAttention claims near-linear time attention by sampling columns and rows based on two fine-grained parameters: the max column norm of the row-normalized… | ||
| Sublinear-Time Algorithms in Learning | Ronitt Rubinfeld | 35m |
Claims sublinear certification for distribution-dependent agnostic learning: tester-learner pair procedures certify use of agnostic learners for decision lists… | ||
| Large Scale Private Learning on Data Streams, and the BLTs | Abhradeep Guha Thakurta | 30m |
Introduces a streaming noise construction that produces the correlated Gaussian noise for DP-FTRL with a buffer cost of about log^2(training steps)×dimensions… | ||
| Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring | Sepehr Assadi | 34m |
Presents a randomized algorithm that outputs a Delta+O(log n) coloring in O(m log Delta) expected time, using ideas from McGregor (streaming) and… | ||
| Linear and sublinear algorithms for graphlet sampling | Marco Bressan | 33m |
Gives two concrete algorithms: one with linear-time preprocessing (compute a total order by repeatedly removing a max-degree vertex) that produces exactly… | ||
| Sublinear algorithms in social networks via core-periphery decomposition | Omri Ben-Eliezer | 40m |
A practical pipeline builds a hierarchical core-periphery decomposition via greedy neighbor-list queries (API-style, rate-limited), producing a sublinearly… | ||
| Sublinear time algorithms for better than 1/2 approximation algorithms for max-cut on expanders | Akash Kumar | 32m |
Algorithm works in the adjacency-list query model on bounded-degree d‑regular graphs and distinguishes MC(G) ≥ 1−γ versus ≤ 1/2+γ using random walks… | ||
| Streaming Algorithms for Connectivity Augmentation | Ali Vakilian | 34m |
Presents single‑pass streaming algorithms and matching lower bounds: link‑arrival k‑CAP gets a 2+ε approximation using O(n/ε · log n) space and shows any <2… | ||
| Talk By Ilya Mironov (Google Brain) | Ilya Mironov | 25m |
Defines the Adversarial Sketch Model where edge devices share no secret, shows equality testing suffers a quadratic lower bound on sketch size via reductions… | ||
| Applications of Sub-linear Algorithms on Other Fields | Vladimir Braverman | 31m |
Argues for applying sublinear methods to medical imaging with concrete results and open problems: using coresets and importance sampling to approximate… | ||
| Hypothesis selection with computational constraints | Maryam Aliakbarpour | 32m |
Presents a concrete, nearly-linear-time procedure that attains a 3·OPT guarantee (plus O(ε)) for proper hypothesis selection while keeping optimal sample usage… | ||
| Lightning Talks | Paul Valiant | 01h 39m |
New result: a polynomial‑time algorithm for high‑dimensional mean estimation that matches Gaussian sample‑error up to a 1+o(1) factor in constant dimension… | ||
| A Bi-metric Framework for Fast Similarity Search | Piotr Indyk | 38m |
Proposes a bi-metric pipeline that builds indices with a cheap proxy (Euclidean embeddings, sketched) and queries with an expensive ground-truth (cross-encoder… | ||
| nothing matches | ||