Mark Jerrum, Alistair Sinclair (UC Berkeley) and Eric Vigoda (Georgia Tech) received the Association for Computing Machinery (ACM) Test of Time Award at a virtual ceremony on Wednesday 23 June at the annual ACM Symposium on Theory of Computation (STOC). The award was made in recognition of their paper A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, which they had presented at the STOC meeting two decades earlier.
The permanent of an n by n matrix is defined by an expansion that is identical to the familiar Leibniz formula for the determinant of a matrix, except that all terms have positive sign. The determinant is preserved by a rich collection of matrix operations, which allows it to be computed easily, for example, by Gaussian elimination. The permanent is preserved by a smaller collection of operations and appears to be correspondingly harder to compute. Indeed, under standard complexity-theoretic assumptions, the permanent of a matrix cannot be computed using a number of arithmetic operations that is polynomial in n. Although the permanent is not as ubiquitous as the determinant, it does arise as the generating function for perfect matchings in a bipartite graph (also known to physicists as the partition function of the dimer model), or of cycle covers of a directed graph.
In the STOC paper from 2001, Jerrum et al. showed how to approximate the permanent of an n by n matrix with non-negative entries within any specified ratio in time polynomial in n. Their approach was via Markov chain Monte Carlo (MCMC), but with a twist. In classical MCMC, samples are drawn from a rapidly mixing Markov chain in near-equilibrium. Here, instead of a single Markov chain, the algorithm generates a sequence of Markov chains by an iterative process. The transition probabilities of each Markov chain in the sequence are deduced from samples obtained by simulating the previous one. As can be imagined, the polynomial bounding the runtime of the resulting algorithm has a fairly large exponent. Even two decades on, no practical algorithm for approximating the permanent of a general non-negative matrix is known.
Another open question is whether there is a polynomial-time algorithm for approximating the number of perfect matchings in a general graph. (The permanent counts perfect matchings in a bipartite graph.) Since the d-dimensional square lattice can be given a checkerboard colouring, it is possible (in theory!) to efficiently approximate the partition function of the dimer model on fragments of the square lattice in any dimension. But no feasible approach to approximating the dimer partition function is known in general.