Approximate Deterministic Counting via Marginal Entropy Optimization
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Deterministic algorithm maximizes the sum of marginal entropies over the matroid base polytope via convex optimization (using a separation oracle) and exponentiates the optimum to get a count estimate. Proof uses LA-concave generating polynomial facts (Hodge-theoretic / log‑concavity), Jensen and capacity inequalities to show the estimate is within a factor 2 in entropy and yields both a sqrt‑approximation and at worst a 2^{rank} multiplicative approximation for matroid bases, extending to intersections of two matroids.
AI-written summary · about