Something for Almost Nothing: Advances in Sub-Linear Time Algorithms
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Algorithms decide properties and approximate values without reading all data by sampling, random orderings, and simulating local procedures. Key concrete claims: uniformity testing over a domain of size n needs Theta(sqrt(n)) samples via collision/L2 estimates; testing closeness of two unknown distributions requires Theta(n^{2/3}) samples; additive distance estimation and support-size estimation need Theta(n / log n) samples. Bounded-degree graphs admit constant-time 2-approximate vertex cover via maximal-matching oracles using random edge orderings with short dependency chains.
AI-written summary · about
chapters (5)
- 0:00Introduction to sublinear data
- 3:07Property testing
- 13:34Classical approximation
- 22:16Local computation algorithms
- 27:45Distribution testing
related talks
35mSublinear-Time Algorithms in Learning
01h 01mNearest Neighbor Methods II
54mA Near-Linear Time Algorithm for the Chamfer Distance
29mTesting Probability Distributions using Conditional Samples
01h 05mNearest Neighbor Methods I
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
23mTowards Practical Distribution Testing