Yale’s Daniel Spielman wins Held Prize for solving decades-old problem

The National Academy of Sciences (NAS) has presented the 2021 Michael and Sheila Held Prize to Daniel Spielman, Sterling Professor of Computer Science and professor of statistics and data science, for helping to solve a theoretical problem that had vexed mathematicians for decades.

The Held Prize honors outstanding, innovative, creative, and influential research in combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complex theory.

Spielman shares the award with Adam W. Marcus of the École polytechnique fédérale de Lausanne in Switzerland and Nikhil Srivastava of the University of California, Berkeley.

Spielman, Marcus, and Srivastava received international attention after publishing new constructions of Ramanujan graphs, that describe sparse, but highly-connected networks, and a solution to what is known as the Kadison-Singer problem, a decades-old problem that asks whether unique information can be gleaned from a system in which only some of the features can be observed or measured. The solution has relevance for a number of fields, including pure mathematics, the mathematical foundations of quantum physics, and computer science.

The trio began working on these questions in 2009 when they were all at Yale.

Their groundbreaking papers on these questions, both published in 2015, solved problems that mathematicians had been working on for several decades,” NAS said in announcing the prize. “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 in the past decade. The 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.”

Spielman said his initial reaction to receiving the Held Prize was “complete surprise.”

“We had no idea we were being considered for the Held Prize,” he said. “It is very nice to receive it for this work, because it rewards the biggest gamble I have made in my career and because it was the result of an exhilarating collaboration that lasted many years.”

Spielman, who joined the Yale faculty in 2006 as a professor of applied mathematics and computer science, is a 1992 summa cum laude graduate of Yale.

In 2013, he received a MacArthur Fellowship, popularly known as the “genius” grant, from the John D. and Catherine T. MacArthur Foundation. He was awarded the 2010 Rolf Nevanlinna Prize from the International Mathematical Union, the 2009 Fulkerson Prize, and, on two occasions, the Gödel Prize for outstanding papers in the area of theoretical computer science. He is also a member of the NAS.