Computing Partition Functions in Hard Problems of Combinatorial Enumeration
Wednesday, November 12, 2014 - 9:00am - 9:50am
As is well known, many interesting problems of combinatorial enumeration are computationally hard (for example, it is hard to approximate the number of independent sets of a given size in a given graph within any non-trivial factor). A smoothed version of a counting problem consists in computing the corresponding partition function (for example, we compute the weighted sum over all subsets of vertices of a given size in a given graph, where the weight of a subset is exponentially small in the number of edges that it spans). It turns out that partition functions can be efficiently computed for many hard enumeration problems (counting independent sets, dense subsets, perfect matchings in hypergraphs, Hamiltonian cycles in graphs), which allows one to make non-trivial conclusions about the original enumeration problem (such as to distinguish graphs that are far from having an independent set of a given size from graphs that have sufficiently many independent sets).