Gödel Prize - 1996

Mark Jerrum, 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:

Alistair Sinclair, Mark Jerrum:
"Approximate counting, unform generation and rapidly mixing Markov chains"
Information and Computation 82 (1989), 93-133

Mark Jerrum, Alistair Sinclair:
"Approximating the permanent"
SIAM Journal on Computing 18 (1989), 1149-1178

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.

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.