Dan Spielman, a Yale computer scientist, wanted to model complex online communities like Facebook, hoping to gain insight into how they form and interact. That's one of the precepts of Science 2.0, understanding how people can participate and scientists can collaborate without being drowned in a lot of 'noise' before being put on the right path to either.

A colleague in Jerusalem observed that aspects of Spielman’s research brought to mind a math problem that had been stumping people since Dwight Eisenhower was in office — the Kadison-Singer math problem. The 1950s? A puzzle that wasn't even from a paper, but from the “Related Questions” section of a paper on extensions of pure states? 

It looked low-hanging fruit — but that turned into a five-year journey. 

First posed in 1959, the Kadison-Singer problem asks, at its core, if unique information can be extrapolated from a scenario in which not all features can be observed or measured(1). The idea is particularly relevant to abstract fields like quantum physics, operator theory, complex analysis, graph theory, signal processing, and finite-dimensional geometry. In these fields, it is often impossible to quantify every characteristic of a system. You can see why Science 2.0 has been struggling to create a method more robust than a text adventure.


Richard Kadison. Konrad Jacobs, Erlangen, Copyright is MFO - Mathematisches Forschungsinstitut Oberwolfach, used under creative commons. Link: Wikipedia

Its origin was quantum physics, where you might want to know three things about a particle — position, spin, and momentum. It is known that by measuring spin and position, you can calculate the particle’s momentum as well, though its exact value cannot be observed. Proving the Kadison-Singer problem meant confirming that this always happens, for every physical system, making it possible to determine unobservable events from observable events.

For Spielman, it meant an improved ability to model interactions among groups within complex networks. In his original models, the interactions between groups were all equal. By proving that the Kadison-Singer conjecture was correct, he could strengthen or weaken interactions between different communities to more realistically model virtual networks.

So, in June 2013, when Spielman and co-authors Adam Marcus, and Nikhil Srivastava publicly posted a proof of the Kadison-Singer conjecture, it was not only a triumph for them, but also great news for a variety of scholars and technologists, and certainly on Science 2.0. 

In the last year, Spielman and collaborators have traveled the world to give more than 100 talks on their work, in cities ranging from Boston to Bordeaux to Bangalore. The Society for Industrial&Applied Mathematics has awarded them George Pólya Prize.

Polynomials and their roots

The work began in 2009, when Adam Marcus was a newly appointed Gibbs Assistant Professor in Applied Mathematics and Nikhil Srivastava was a graduate student working in Spielman’s group. Together, Marcus, Srivastava, and Spielman broke the problem into three parts, all dealing with the roots of certain polynomials, or the values of x when y is equal to zero in a mathematical relationship such as y=3x2+6x+12.

Part 1 required the team to prove that all of the roots for these polynomials are real numbers, and part 2 required that the three prove the roots of certain polynomials interlace, or alternate in ascending order. For example, if one polynomial has roots 1, 4, and 8 and another has roots 0, 2, and 7, then they interlace.

Within a year the team members had worked through the first two parts and felt confident they could tackle the third part as quickly: demonstrating that there are upper bounds limiting the magnitude of the alternating polynomial roots.

“Parts one and two were always easier for us because they were fundamentally qualitative,” said Spielman. “There are fairly general techniques for proving qualitative statements like ‘polynomial p(x) is real-rooted.’ On the other hand, proving bounds on how large the roots of certain polynomials can be involved fairly intricate computations. To solve part three we had to come up with a very novel way of reasoning about where the roots of polynomials can lie.”

Years passed and life changed. Srivastava took a position with Microsoft Research in India. Marcus joined Crisply, a start-up company in Cambridge, Massachusetts, that allowed him to devote an entire day each week to working on the Kadison-Singer problem. And Spielman came to international attention after he was named a MacArthur Fellow. But the Kadison-Singer problem remained a constant for them all.

“We could never get excited on working on other problems,” said Spielman, who at Yale is professor of computer science, mathematics, and applied mathematics. “The Kadison-Singer problem was just too interesting and compelling: Every approach we pursued revealed beautiful structures. When you are following an approach to a math problem and you discover something beautiful, you take it as an indication that you are on the right path. We kept getting that feeling.”

Even though Spielman, Marcus, and Srivastava did not want to stray from their work on the Kadison-Singer problem, the pressure to publish was increasing. The team decided to take a slight detour to investigate Ramanujan graphs, which describe very sparse networks that are still highly connected. These graphs were often counterintuitive, required deep and difficult mathematics, and were only informative for a small subset of networks. Spielman, Marcus, and Srivastava thought the work they’d already done on the Kadison-Singer problem would yield simpler proofs for Ramanujan graphs that would apply to a larger number of networks.

They were correct.


Nikhil Srivastava, Adam Marcus, Dan Spielman. Credit: Yale University

What the team wasn’t expecting was that Ramanujan graphs were, in fact, the key to the frustrating third part of the Kadison-Singer problem. By expanding the applications of Ramanujan graphs, Spielman, Marcus, and Srivastava gained insight on how to approach the challenging third part of the Kadison-Singer problem.

“I just started laughing,” said Srivastava. “The solution fit together so beautifully and sensibly you knew it was the 'right' proof and not something ad hoc. It combined bits of ideas that we had generated from all over the five years we spent working on this.”

Although the proof of the Kadison-Singer problem has received the majority of the attention, the work done by Spielman and his team on the second part of the problem, interlacing polynomials, is driving the team’s future work.

“Adam and Nikhil and I will be writing papers with two more applications of the technique this summer,” said Spielman.

Source: Holly Lauridsen, Yale News

(1) See SoulPhysics.org

Kadison-Singer Conjecture. Let  be a discrete maximal abelian subalgebra of , the algebra of bounded linear operators on a separable Hilbert space. Let  be a pure state on that subalgebra. Then there exists a pure extension  of to all of , and that extension is unique.