Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved

The permanent of an n x n matrix A with 0-1 entries aij is defined by per (A) = Σ/σ Π/n-1/i=ο aiσ (i), where the sum is over all permutations σ of n = 0, …, n - 1. Evaluating per (A) is equivalent to counting perfect matchings (1-factors) in the bipartite graph G = (V1, V2, E), where V1 = V2 = n and (i, j) ∈ E iff aij = 1. The permanent function arises naturally in a number of fields, including algebra, combinatorial enumeration and the physical sciences, and has been an object of study by mathematicians for many years (see 14 for background). Despite considerable effort, and in contrast with the syntactically very similar determinant, no efficient procedure for computing this function is known.