Geometry and Complexity of Counting

I am going to describe a general approach to obtain fast and crude bounds on the cardinality of combinatorially defined sets, such as perfect matchings in a given graph, trees and forests with special properties, non-degenerate submatrices of a given matrix, etc. The idea of the approach is to identify the set of interest with a subset of a certain metric probability space (most often, the Boolean cube) and measure the distance from a random point in the space to the set, hoping that the distance will be small if and only if the set is large. In many interesting cases the distance can be computed quite easily by known combinatorial optimization algorithms. The talk is based on a paper joint with A. Samorodnitsky.