Abstract
I will present a framework for deterministic approximate counting in discrete structures where linear optimization is easy; these include matroids and their pairwise intersections. The key to the performance of this framework is a set of inequalities lower and upper bounding the entropy of probability distributions on these structures in terms of entropies of their projections/marginals. The lower bounds can be though of as an analog of the Van der Waerden's lower bound on the permanent of doubly stochastic matrices, and are related to log-concave polynomials. The upper bounds are related to the subadditivity of entropy. Time-permitting I will also discuss improved versions of these inequalities in the important special case of bipartite perfect matchings/permanent, which has led to the current best approximation ratio of 2^{n/2}. Based on joint works with Shayan Oveis Gharan, Cynthia Vinzant, and Alireza Rezaei.