Yale News

Daniel Spielman, Sterling professor of computer science and professor of statistics and data science and of mathematics, received the Michael and Sheila Held Prize for work that he and his fellow researchers began while at Yale.

The Held Prize, announced on Jan. 21, is awarded by the National Academy of Sciences for innovative research in certain areas of computer science related to designing, optimizing and analyzing algorithms. Spielman, with postdoc Adam Marcus — now a professor at École Polytechnique Fédérale de Lausanne — and graduate student Nikhil Srivastava — now a professor at University of California, Berkeley — won the award for their 2015 breakthrough proof of the Kadison-Singer conjecture. This was an important and then-unsolved problem with implications in fields ranging from quantum physics to engineering. They also received recognition for their work on Ramanujan graphs, which are related to many advances in theoretical computer science.

“We were using a very different area of mathematics and very different set of techniques than the people who had been thinking about this problem,” Spielman said. “The people who are really working on this stuff found our solution very strange.”

The Kadison-Singer conjecture, posed by mathematicians Richard Kadison and Isadore Singer in 1959, was originally inspired by work done on the mathematical foundations of quantum mechanics. However, the problem was soon found to have equivalent and similarly unsolved problems in many other fields, such as computer science.

One of these equivalent conjectures proposes that, in simple terms, if one takes a large network whose vertices are all connected via edges and then classify those edges into two approximately equal groups — for example, coloring some edges red and others blue — it is possible to do so in a way that still allows all vertices to be sufficiently interconnected even when solely using either blue or red edges. The Kadison-Singer problem consisted of proving or disproving this conjecture.

Spielman and Srivastava had previously studied how to simplify a network to maintain comparable interconnectivity while reducing the number of connections. In a conversation with Spielman, Gil Kalai, a mathematician at the Hebrew University of Jerusalem and visiting professor at Yale, pointed out the similarities between Spielman and Srivastava’s discoveries and the Kadison-Singer conjecture.

“I thought at the time, not only does what we’re doing look like that problem, but we think we can solve that problem,” Spielman said. “I thought it wouldn’t take very long, and … yeah, I was completely wrong about that. It took about five years.”

Spielman, Srivastava and Marcus — who joined them six months into the project — spent the first four of those five years developing a number of novel techniques for tackling the Kadison-Singer conjecture. During their fourth year of work, the group started to wonder if they could prove the conjecture at all. And to make use of their new techniques, they applied those methods to prove a different theory about networks called Ramanujan graphs.

With a new perspective gained from their work on Ramanujan graphs, the team was then able to prove the Kadison-Singer conjecture using those same techniques.

“Dan [Spielman] and his team solved this problem by a surprising method, motivated by the probabilistic method in combinatorics,” Professor of Mathematics Van Vu wrote in an email to the News. “All in all, it is a first-rate achievement.”

Spielman and his colleagues’ result has been hugely influential in mathematics and computer science research — not only because of the implications of the conjecture, but also due to the breakthroughs in the proof itself. According to Spielman, the techniques that they developed to prove the Kadison-Singer problem have made way for further progress on the famously difficult “traveling salesman problem,” which also relates to networks — specifically, finding an algorithm to travel between different cities on a network of roads in the shortest way possible.

Since the publication of their proof in 2015, both Marcus and Srivastava have continued to do research related to the Kadison-Singer problem.

Srivastava’s recent work has strengthened the team’s original statement that proved the Kadison-Singer conjecture. They initially proved that there exists a partition that can divide a network roughly in half while maintaining much of that network’s original connectivity. While the exactness of the split depends on the characteristics of the network, Srivastava proved that the resulting groups can each be closer to exactly one-half of the original network than was previously believed.

Srivastava, along with other researchers, has also developed an algorithm to find these network partitions. But although the algorithm is faster than the method of exhaustively evaluating all possibilities, it is still not very fast.

“What we discovered in [creating this algorithm] was that there were some serious obstacles to making our proof of Kadison-Singer efficient,” Srivastava said. “You would need a significantly different proof to turn that into an algorithm.”

Meanwhile, Marcus has been studying the techniques that they invented for the original proof: “pushing the technology a little further,” as he put it, to see what other problems he can solve.

Because these techniques were so unexpected when used for the Kadison-Singer problem, he has also been working on relating them to other concepts that are familiar to more mathematicians.

“I spent maybe the next five or six years trying to develop that story for them,” Marcus said. “To say, here’s the things that you guys do that are kind of like the things that we do.”

Spielman was named a MacArthur Fellow in October 2012 and was elected to the National Academy of Sciences in 2017.

Isabelle Qian | isabelle.qian@yale.edu

Olivia Fugikawa | olivia.fugikawa@yale.edu

• Yale joins as research partner in $25 million Quantum Leap Challenge Institute