Gödel Prize - 1996
Mark Jerrum, Alistair SinclairThe 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:
Alistair Sinclair, Mark Jerrum:
Mark Jerrum, Alistair 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.