Model Counting Meets Distinct Estimation
summary
Shows a concrete recipe that translates streaming F0 sketches into model-counting procedures and back, replacing streams by Sol(phi) and sketches by constraints solved with NP calls. Uses pairwise XOR hashes (2‑wise independent hash families), sketches like the bucket‑level sketch and min‑hash, and reconstructs them by polynomially many SAT/XOR queries to get ε,δ approximate counts. Consequences: new model counters (including FPRAS for certain DNF families), a tradeoff mapping streaming space to NP‑query complexity, and lifted distributed lower bounds.
AI-written summary · about
chapters (19)
- 0:00Model counting basics
- 1:12Model counting problem
- 3:21Distinct elements in streams
- 5:49History of both problems
- 7:34Approx counting algorithm
- 9:31Distinct elements algorithm
- 11:59Streaming to counting
- 13:27Sketching approach
- 16:15Applying the recipe to the minimum hash algorithm
- 19:31Bucketing for distinct
- 21:41Bucketing to counting
- 23:55Polynomial-time implications
- 25:00Space and query links
- 26:47Counting to streaming
- 29:04Interval union & DNF
- 30:34Conclusion & future work
- 31:58Q&A session part one
- 34:58Q&A session part two
- 37:51Q&A session part three
related talks
01h 24mStreaming, Sketching and Sufficient Statistics I
55mTheory of Data Streams
27mImproved Frequency Estimation Algorithms with and without Predictions
10mDon’t forget to sketch! Running with large datasets
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 50mData sketching workshop
01h 13mSketching High-Dimensional Data
43mResizable Sketches