in polynomial time. 2003: J. F. Geelen, A. M. H. Gerards and A. Kapoor for the GF(4) case of Rota's conjecture on matroid minors. Bertrand Guenin for a forbidden minor characterization of the weakly bipartite graphs (graphs whose bipartite subgraph polytope is 0-1). Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and Alexander Schrijver for showing submodular minimization to be strongly polynomial. 2006: Manindra Agrawal, Neeraj Kayal and Nitin Saxena, for the AKS primality test. Mark Jerrum, Alistair Sinclair and Eric Vigoda, for approximating the permanent. Neil Robertson and Paul Seymour, for the Robertson–Seymour theorem showing that graph minors form a well-quasi-ordering. 2009: Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for the strong perfect graph theorem. Daniel A. Spielman and Shang-Hua Teng, for smoothed analysis of linear programming algorithms. Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture on the densest possible sphere packings. 2012: Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving the approximation ratio for graph separators and related problems from to . Anders Johansson, Jeff Kahn, and Van H. Vu for determining the threshold of edge density above which a random graph can be covered by disjoint copies of a given smaller graph. László Lovász and Balázs Szegedy for characterizing subgraph multiplicity in sequences of dense graphs. 2015: Francisco Santos Leal for a counter-example of the Hirsch conjecture. 2018: Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Böttcher for The chromatic thresholds of graphs Thomas Rothvoss for his work on the extension complexity of the matching polytope. 2021: Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, and Andrew Treglown for Proof of the 1-factorization and Hamilton decomposition conjectures Jin-Yi Cai and Xi Chen for Complexity of Counting CSP with Complex Weights Ken-Ichi Kawarabayashi and Mikkel Thorup for Deterministic Edge Connectivity in Near-Linear Time See also List of mathematics awards References External links Official web page (MOS) Official site with award details (AMS website) AMS archive of past prize winners Computer science awards Awards of the American Mathematical Society Triennial events 1979 establishments in the United States