Effort to model Facebook yields key to famous math problem (and a prize)
Dan Spielman, a Yale computer scientist, wasn’t looking for a new problem. He was already deeply immersed in a tricky effort to model complex online communities like Facebook, hoping to gain insight into how they form and interact.
But when a colleague in Jerusalem observed that aspects of Spielman’s research brought to mind the famous — and unsolved — Kadison-Singer math problem, Spielman saw irresistibly low-hanging fruit — or so it seemed.
“The Kadison-Singer problem looked so close to something we already knew to be true and was, in fact, identical to something we conjectured to be true in our work,” Spielman said. “We thought we should be able to prove it.”
The side project evolved into a five-year journey, and yielded a solution to the famous problem, which had baffled mathematicians since the Eisenhower administration.
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. The idea is particularly relevant to abstract fields, including 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.
For example, in quantum physics, 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, even 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, a solution to the Kadison-Singer problem would improve his 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.
A new approach to the problem
“This is doubly exciting, because they have proved an important conjecture and they did it by introducing a whole new approach to doing such proofs,” said Holly Rushmeier, chair of Yale’s computer science department. “This won’t be the last big news to come out of this line of research.”
The solution has also put the Yale computer science and math departments in the international spotlight: 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. Accolades have poured in, most recently from the Society for Industrial & Applied Mathematics, which this month (July) will award the three scientists the George Pólya Prize.
The accolades have been a long time coming for the team, which began its work 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.
Polynomials and their roots
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.”
Knew they were on ‘the right path’
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.
The solution fit ‘so beautifully’
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.