Effort to model Facebook yields key to famous math problem (and a prize)

July 8, 2014
Effort to model Facebook yields key to famous math problem (and a prize)
Srivastava, Marcus, and Spielman (left to right) soon after completing the proof of the Kadison-Singer Problem.

(Phys.org) —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 , 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.

Explore further: Indian researcher helps prove math conjecture from the 1950s

Related Stories

Indian researcher helps prove math conjecture from the 1950s

July 17, 2013

On June 18, Adam Marcus and Daniel A. Spielman of Yale University, along with Nikhil Srivastava of Microsoft Research India, announced a proof of the Kadison-Singer conjecture, a question about the mathematical foundations ...

Professor works to shrink error margins in US census data

April 24, 2013

A person searching through the massive expanse of data collected by the U.S. Census Bureau in search of details about a specific neighborhood may increasingly find statistics with colossal margins of error, such as an average ...

What studying networks can tell us about the world

February 12, 2014

There was an opening ceremony on Feb. 5 for the Yale Institute for Network Science (YINS), dedicated to exploring fundamental properties of networks as they appear throughout the biological, physical, and social sciences.

Recommended for you

Scientists see order in complex patterns of river deltas

October 19, 2017

River deltas, with their intricate networks of waterways, coastal barrier islands, wetlands and estuaries, often appear to have been formed by random processes, but scientists at the University of California, Irvine and other ...

Fatty bird gland preserved over 48 million years

October 18, 2017

(Phys.org)—A team of researchers from the U.S., Ireland, Germany and the U.K. has found evidence of preservation of a fatty oil gland from a 48-million-year-old fossilized bird. In their paper published in Proceedings of ...

Waiting periods reduce deaths from guns, study suggests

October 17, 2017

(Phys.org)—A trio of researchers with Harvard Business School has found evidence that they claim shows gun deaths decline when states enact waiting period laws. In their paper published in Proceedings of the National Academy ...


Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (1) Jul 08, 2014
I can almost taste the power of this article, almost. I totally get the happy grins on the faces in the photo at the beginning of the article. I just wish I wasn't so mathematically challenged.
3.7 / 5 (3) Jul 08, 2014
A math professor teaching a seminar says: "it is obvious that...hmmm" then gets an abstracted look, as if in another world. He begins muttering to himself and slowly walks out.

The grad students, having seen this before, go to lunch, and one who had the professor as an advisor goes to see the dean, who in turn assigns a new advisor and files the paperwork for his professor to go on extended sabbatical.

Five years later, with a slightly swifter pace, the professor strides back into the seminar room. Not noticing that there are now a completely different set of students there, the professor announces: "Yes, it is obvious that ..."

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.