Domain Sparsification of Discrete Distributions using Entropic Independence

on YouTube ↗22m

" summary

Proves that for any distribution satisfying entropic independence with parameter alpha a preprocessed sampler reduces the ground set from N to about N^{1-alpha} times poly(K), giving one-step TV error ≤0.1 and thus O(log(1/epsilon)) iterations to get epsilon accuracy. Works with only constant-factor estimates of marginals, applies to symmetric and non-symmetric DPPs, spanning trees and k-matchings, and yields faster approximate counting (e.g., size-K matchings in planar graphs). Shows matching lower bounds (birthday-paradox threshold N^{1-1/K} in the worst case).

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:24Sampling from discrete distributions
3. 1:27Counting by repeated sampling
4. 3:43Determinantal Point Processes (DPPs)
5. 5:35A brief history
6. 7:11Sampling from continuous distributions
7. 8:22Outline
8. 9:25Converting to isotropic position
9. 10:29Simple idea: Intermediate sampling
10. 11:05Markov chain intermediate sampling
11. 12:21Example: Bipartite graph
12. 13:04In general: Birthday paradox for k-collisions
13. 14:09Generating polynomial
14. 16:09Entropic independence: examples
15. 17:29Domain sparsification: A general framework
16. 17:50Application
17. 18:26Domain size is tight!
18. 18:50High level proof idea
19. 20:39Conclusions
20. 21:08Open problem