Counting and Optimization Using Stable Polynomials
summary
Shows that for distributions whose generating polynomial is real-stable the log of the set size is approximable by the sum of edge marginals up to a factor-of-two entropy bound and by an additive O(n) error; uses Gurvits-style real-stable generating polynomial arguments, log-concavity and a convex program over marginals solved with a separation oracle when available. Applies to spanning trees, determinantal measures, bipartite matchings via matrix scaling, gives randomized PTAS in some cases but only exponential deterministic guarantees in general.
AI-written summary · about