Homomorphic Sketches: Shrinking Big Data without Sacrificing Structure
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Shows a recipe to compress each row of an n-by-n adjacency matrix into polylog(n) bits per node by encoding signed incidence vectors and applying an L0-sampling linear projection m so that sums of sketches reveal a nonzero edge across any cut. Emulates a log n‑round edge‑picking algorithm to recover a spanning forest, extends to sample edges with probability ~t/cond(e) to build cut sparsifiers (and, with larger space, spectral sparsifiers). Separately proves cyclic‑rotation fingerprints require and achieve ~d(n)·polylog n bits, where d(n) is number of divisors.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:34Sketches
- 1:12Linear Sketches
- 3:30Theme
- 5:06Communication
- 5:41Connectivity Properties
- 9:39Fingerprinting Sketches
- 12:39Connectivity
- 13:09Graph Streaming
- 14:09Connectivity Algorithm
- 16:29Homomorphic Sketches Recipe
- 21:24Homomorphic Sketches Algorithm
- 24:54Effective Resistance
- 45:50Summary
related talks
01h 13mSketching High-Dimensional Data
01h 09mSketching High-Dimensional Data
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 21mAn Overview on Data Streams Algorithms
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 10mSketching High-Dimensional Data
01h 04mSampling Big Ideas in Sublinear Algorithms