Entropy, Capacity, and Counting
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22·
summary
Generalizes Gurvits' capacity to compute sums of polynomial coefficients over a polytope and gives a concrete algorithmic claim: with an oracle to evaluate the polynomial and a separation oracle for the polytope, one gets deterministic approximate counting within multiplicative error via an entropy-based relaxation and convex duality. Tools: real-stable polynomial facts, a dual entropy program, and the ellipsoid method; key technical bound shows an ε-approximate dual lies inside a ball of radius poly(M, log(1/ε)), making the method effective.
AI-written summary · about
chapters (9)
- 0:00ENTROPY, CAPACITY, and COUNTING
- 2:25Counting, Polynomials, and Polytopes
- 8:58Perfect Matchings in Bip. Graphs
- 14:35Entropy and Counting a la Boltzmann
- 33:05Entropy Interpretation of Capacity
- 33:31Computing the Capacity via Ellipsoid
- 45:10Bounding Box 1
- 49:54Summary and Challenges
- 52:20Bounding Box 2
related talks
49mRecent Advances in Counting Sparse Graphs
01h 00mAverage-case Complexity for Polynomials, and All That
29mExtended Formulations and Information Complexity
39mOptimization over the Hypercube via Sums of Nonnegative Circuit Polynomials
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
38mAn Information Theoretic View of Hypercontractivity
27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces