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: think of the row and column operations from Linear Algebra I or Linear Algebra II! The existence of these operations allows the determinant to be computed rapidly, for example, by Gaussian elimination. The permanent is preserved by a smaller collection of operations, and it appears to be correspondingly harder to compute. Indeed, under the assumption P ≠ NP, which you may have come across in popular science articles, the permanent of a matrix requires time exponential in n to compute!
Although the permanent is not as pervasive as the determinant, it does arise in statistical physics as the partition function of the so-called dimer model. Physicists are interested in partition functions, as many properties of physical models can be deduced from them.
In their 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). In classical MCMC, samples are drawn from a rapidly mixing Markov chain in near-equilibrium. Those who are familiar with Markov chains, perhaps through having taken the Random Processes module, know that a Markov chain may have a limiting distribution. The term `rapidly mixing’ indicates that a Markov chain not only converges to this limiting distribution, but does so quickly. For obvious reasons, rapid mixing is a key property in algorithmic applications. In the current application of MCMC to estimating the permanent of a matrix, there is a twist, which is that the Markov chain itself is arrived at via a stochastic process! Although efficient in a strictly theoretical sense (i.e., in the sense of taking polynomial versus exponential time), this algorithm for the permanent is not practical. Indeed, to date, no practical algorithm for estimating the permanent of a matrix has been devised. It is an open question whether such an algorithm exists.
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.) Those who followed the Algorithmic Graph Theory module may have picked up on the fact that matching in general graphs is harder than matching in bipartite graphs.
It is not always the case, but sometimes a piece of mathematical research may pick up on several concepts familiar from undergraduate modules, as this example illustrates.