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.