1996 Gödel Prize

1996 Gödel Prize

Mark Jerrum and Alistair Sinclair

The 1996 Gödel Prize for outstanding journal articles in the area of theoretical computer science was awarded on May 23, 1996 jointly to Mark Jerrum and Alistair Sinclair for their papers "Approximate counting, unform generation and rapidly mixing Markov chains," Information and Computation 82 (1989), 93-133, by Sinclair and Jerrum, and "Approximating the permanent," SIAM Journal on Computing 18 (1989), 1149-1178, by Jerrum and Sinclair.

The first paper demonstrates a two-way connection between the mixing rate of a Markov chain and a graph-theoretic quantity called conductance, and provided the canonical paths tool for establishing high conductance. The second paper then brilliantly applies this method to prove the rapidly mixing property of a certain random walk on the set of all perfect matchings of a dense graph, thereby providing a polynomial time algorithm for approximating the permanent. Together, these two papers have helped trigger a Markov Chain "renaissance" in the 1990's, and one can conservatively count seventy major papers employing Markov chains in the style and methodology they initiated, covering areas as diverse as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. In terms of their innovation and far reaching impact, the Jerrum-Sinclair papers are worthy of a prize named after Kurt Gödel.


Created by Ian Parberry, March 25, 1999.
Last updated Thu Mar 25 10:06:23 CST 1999.