22.01.21 – EPFL Professor Adam W. Marcus, head of the Chair of Combinatorial Analysis, and colleagues Professors Daniel A. Spielman (Yale University) and Nikhil Srivastava (University of California, Berkeley) won the 2021 Michael and Sheila Held Prize for their revolutionary work on the Kadison-Singer problem and Ramanujan graphs. The award is presented with a $100,000 prize.

Marcus, Spielman, and Srivastava solved longstanding questions on the Kadison-Singer problem and on Ramanujan graphs, and in the process uncovered a deep new connection between linear algebra, geometry of polynomials, and graph theory that has inspired the next generation of theoretical computer scientists.

Their groundbreaking papers on these questions, both published in 2015, solved problems that mathematicians had been working on for several decades. In particular, their solution to the Kadison-Singer problem, first posited in 1959, has been hailed as one of the most important developments in mathematics of the past decade.

Their proofs provided new tools to address numerous other problems, which have been embraced by other computer scientists seeking to apply the geometry of polynomials to solve discrete optimization problems.

The Michael and Sheila Held Prize is presented annually and honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years). The prize was established in 2017 by the bequest of Michael and Sheila Held.