2006 Fulkerson Prize Citation

Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160, No. 2, 2004, Pages 781-793.

Testing whether an integer is a prime number is one of the most fundamental computational and mathematical problems. The existence of short certificates for both compositeness and primality was known since the 70's and suggested that primality testing might be in P. Yet, despite numerous efforts and a flurry of algorithms, it was not until 2002 that Agrawal, Kayal and Saxena devised the first deterministic polynomial-time algorithm for primality testing. Earlier algorithms had either assumed the generalized Riemann hypothesis, or been randomized or had been only subexponential. This is a stunning development. This result is a true masterpiece, combining algebraic and number theoretic results in a seemingly simple way.

Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", J. ACM 51, No. 4, 2004, Pages 671-697.

The permanent of a matrix has been studied for over two centuries, and is of particular importance to statistical physicists as it is central to the dimer and Ising models. For a 0-1 matrix, it represents the number of perfect matchings in the corresponding bipartite graph. Although polynomial-time computable for planar graphs, the computation of the permanent is #P-complete for general graphs as shown by Valiant in 1979. This opened the search for approximation schemes. In this paper, Jerrum, Sinclair and Vigoda give the first Fully Polynomial Randomized Approximation Scheme for computing the permanent of any 0-1 matrix or any nonnegative matrix. This is a remarkable result. Their algorithm is based on updating a Markov chain in a way that quickly converges to a rapidly mixing non-uniform Markov chain on perfect matchings and near-perfect matchings. Their work builds upon the earlier pioneering work of Jerrum and Sinclair who initiated the use of rapidly mixing Markov chains for combinatorial problems.

Neil Robertson and Paul D. Seymour, "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory Series B 92, No. 2 , 2004, Pages 325-357.

Kuratowski's theorem says that a graph is planar if and only if it does not contain K_5 or K_{3,3} as a minor. Several other excluded minor characterizations are known, and Wagner conjectured that any minor-closed graph property can be characterized by a finite list of excluded minors. Restated, this says that for any infinite family of finite graphs, one of its members is a minor of another one. In a remarkable tour de force, Robertson and Seymour proved Wagner's conjecture, and this paper appeared as part 20 of their monumental work on the theory of graph minors. Their proof of the Graph Minor Theorem required the development of many graph theoretic concepts, such as linkages and tree-width. This is a spectacular achievement in graph theory with far reaching consequences. It shows, for example, that embeddability in any fixed surface can be characterized by a finite list of excluded minors, or that the disjoint paths problem can be solved in polynomial time for a fixed number of terminals.