Sketching and Algorithm Design 2023
2023-10-09..2023-10-13
Berkeley, United States
[Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Sublinear Algorithms and Nearest-Neighbor Search, Information Theory, Learning and Big Data (Simons Institute, 2015), Optimization and Algorithm Design 2023, Interactive Complexity 2018, Randomized Numerical Linear Algebra and Applications 2018]
who it's for
theoretical computer scientists, streaming algorithm designers, sketching researchers, machine learning researchers, data structure engineers, graph and combinatorial optimization researchers
topics
Johnson-Lindenstrauss sketches; locality-sensitive hashing for KDE; randomized Kaczmarz sketch-and-project; low-rank attention approximation; random principal submatrix eigenvalue estimation; CountSketch and CountMin variants; streaming k-means and k-median; adaptive sketching for maximum matching; pseudorandom hashing for space-bounded computation; quantum sketches for graph algorithms; frequency estimation with predictions; kernel density estimation via discrepancy methods
| title | author | length |
|---|---|---|
| Randomized Embeddings and Neural Networks | Mert Pilanci | 01h 04m |
Shows that two-layer ReLU training admits an exact convex reformulation with variables polynomial in sample size but exponential in feature rank, and that a… | ||
| Fast Attention Requires Bounded Entries | Josh Alman | 46m |
Shows attention computation has a sharp threshold: if all Q,K,V entries satisfy B ≤ √log n a polynomial-approximation method yields a low-rank decomposition… | ||
| Sketching for Proving Generalization of Support Vector Machines | Kasper Larsen | 46m |
Proves tighter margin-based generalization bounds for binary linear SVMs on linearly separable data by using a randomized Johnson-Lindenstrauss sketch of… | ||
| Sketching Techniques for Kernel Density Estimation | Moses Charikar | 46m |
Presents concrete algorithms that turn kernel density estimation into a sketching data structure using locality-sensitive hashing for distance-biased sampling… | ||
| Lightning Talks | Jelani Nelson | 41m |
Seven three-minute updates cover concrete results: a streaming correlation-clustering multipass implementation and covering-in-streams algorithms with tight… | ||
| Sketching and Projecting | Deanna Needell | 53m |
Shows that sketch-and-project solvers — e.g. randomized Kaczmarz, block Kaczmarz and Gaussian sketch updates — give exponential convergence to a small error… | ||
| Sublinear Time Eigenvalue Approximation via Random Sampling | Cameron Musco | 47m |
Presents a simple algorithm that samples a random principal submatrix of size about O(log^3 n/ε^3) × O(log^3 n/ε^3), scales it, and uses its eigenvalues to… | ||
| Testing Positive Semidefiniteness and Eigenvalue Approximation | David P. Woodruff | 35m |
Presents concrete testers and tight bounds: for Schatten-1 norm, adaptive matrix‑vector Krylov methods use a polynomial filtering trick to get 1/epsilon^{1/3}… | ||
| Improved Frequency Estimation Algorithms with and without Predictions | Sandeep Silwal, Anders Aamand, Justin Y. Chen, Huy Nguyen, Ali Vakilian | 27m |
Tight characterization shows learned CountMin/CountSketch only help when space B is very large; a new algorithm uses many tiny sketches plus one large sketch… | ||
| Capacity Analysis of Vector Symbolic Architectures | Ken Clarkson, Shashanka Ubaru, Elizabeth Yang | 43m |
Paper gives concrete dimension bounds and algorithms: MAP-I reduces to sketching and uses JL-type sign matrices to prove how large m must be for membership and… | ||
| Sketching Algorithms for Max-DICUT and other CSPs | Santhoshini Velusamy | 01h 00m |
Claims a concrete sketching pipeline: compute the L1 bias via an Indyk-style sketch to get a 2/5 approximation, then refine to 4/9 and 0.485–0.486… | ||
| A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching | Sepehr Assadi | 47m |
Presents a concrete algorithm that achieves a (1−ε)-approximation for weighted matching in general (non‑bipartite) graphs using O(log n / ε) rounds of adaptive… | ||
| Tight Bounds for Volumetric Spanners in All Norms | Ali Vakilian, Aditya Bhaskara, Sepideh Mahabadi | 37m |
A simple single-swap local search provably constructs volumetric spanners for all ℓ_p norms: running until no swap increases det(M) by 1+δ yields a spanner of… | ||
| Robustness of Sketches to Adaptive nputs | Edith Cohen | 50m |
Shows how a differential-privacy-style wrapper (replicating sketches, DP aggregation) gives robustness to adaptive inputs and supports about d^2 queries on a… | ||
| A Near-Linear Time Algorithm for the Chamfer Distance | Piotr Indyk | 54m |
Claim: a one-plus-epsilon approximation to Chamfer distance in near-linear time, roughly O(d n log n / ε^2), achieved by computing crude nearest-neighbor… | ||
| Memory-Regret Tradeoff for Online Learning | Binghui Peng, Aviad Rubinstein | 58m |
Shows two concrete tradeoffs and gives matching algorithms and lower bounds: against an oblivious adversary an algorithm using S bits achieves about sqrt(nT/S)… | ||
| Sketching Techniques for Kernel Density Estimation or for Optimal Transport Computations | Erik Waingarten | 48m |
Replaces the Earth Mover objective with an L_rho relaxation (raise gamma entries to rho>1) and optimizes the dual via first‑order methods, estimating gradients… | ||
| Streaming Euclidean k-median and k-means with o(log n) Space | Samson Zhou, Vincent Cohen-Addad, David P. Woodruff | 01h 00m |
Presents a streaming algorithm that breaks the long standing Omega(log(n Delta)) word barrier for insertion-only Euclidean (k,z)-clustering by producing a… | ||
| Streaming Lower Bounds for the Needle Problems | Jiapeng Zhang, Shachar Lovett, Qian Li, Shuo Wang | 44m |
Shows a near-tight lower bound: any streaming algorithm with space s needs about t ≈ 1/(s p^2) samples (multipass adds an l factor) to distinguish uniform vs… | ||
| Error Correction for Streaming Messages | Meghal Gupta | 33m |
Provides an explicit encoding enc(x) of length about n^2 that lets Bob recover f(x) (e.g. y·x) in space s·polylog(n) even under adversarial noise up to δ = 1/4… | ||
| Insights from Engineering Sketches for Production and Using Sketches at Scale | Lee Rhodes | 01h 02m |
Apache DataSketches originates at Yahoo in 2012, now shipping ~15 sketch types across Java, C++ and Python and producing a billion sketches per day in… | ||
| A Simple Quantum Sketch With Applications to Graph Algorithms | John Kallaugher | 57m |
A log-qubit sketch stores several copies of the uniform superposition over set S and answers “how many disjoint pairs from a partition lie inside S” by… | ||
| Resizable Sketches | Rasmus Pagh | 43m |
Proves a lower bound that any one-sided dynamic approximate membership must pay about log log n bits per element at some point, and gives a matching upper… | ||
| Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming | Mikkel Thorup | 57m |
Introduces HashPRG, a symmetric Nisan-style PRG that trades seed length for block-evaluation time and is provably indistinguishable to algorithms using only εB… | ||
| nothing matches | ||