50-year-old problem solved!

In 2008, Daniel Spielman told his colleague, Gil Kalai, that he was working on a problem in computer science, on how to ‘sparsify’ a network, meaning that the network would have fewer connections between nodes, whilst preserving its essential features. Kalai suggested that this problem seemed connected with the Kadison-Singer problem in quantum physics, which had remained unsolved for 50 years. Peter Casazza and Janet Termain of the University of Missouri concluded that this problem had “defied the best efforts of some of the most talented mathematicians of the last 50 years.”

Although Spielman, a computer scientist, knew little of quantum mechanics and C*-algebras (the area of mathematics that this problem concerns), after Kalai described the problem in one of its equivalent forms, he realized that he might be able to solve it.

“It seemed so natural, so central to the kinds of things I think about. I thought, ‘I’ve got to be able to prove that.’”

In 2013, along with the help of Adam Marcus and Nikhil Srivastava, Spielman proved this problem after 5 years.

Nikhil Srivastava Adam Marcus Dan Spielman.jpg
Srivastava, Marcus and Spielman (left to right)

In doing so, the trio had used tools unheard by mathematicians, solving the problem in a “bafflingly foreign” way. Thus, the proof may take several more years to digest and in fact, mathematicians have held several workshops to unite these disparate camps.

What is the Kadison-Singer Problem?

Richard Kadison and Isadore Singer

The Kadison-Singer problem asks how much it is possible to learn about a ‘state’ of a quantum system if you have complete information about that state in a special subsystem. This question builds on Heisenberg’s uncertainty principle.

Why is this problem important?

Network sparsification has many applications in data compression and efficient computation. Additionally, computer scientists have exploited the techniques that were created to solve the problem. For example, last year, two researchers used these tools to make a huge step forward in our understanding of the traveling salesman problem. Assaf Naor, a mathematician at Princeton, asserted that “this [proof] is too profound to not have many more applications.” These applications may become more apparent once mathematicians develop a deeper understanding of the proof.

“What I love about it is just this feeling of freshness,” Naor said, “that’s why we want to solve open problems — for the rare events when somebody comes up with a solution that’s so different from what was before that it just completely changes our perspective.”

The proof of the Kadison-Singer problem implies that quantum knowledge can be extended to full quantum systems, networks can be decomposed into electrically similar ones, and matrices can be broken into simpler chunks. The proof could have some applications in signal processing, since it implies that collections of vectors used to digitize signals can be broken down into smaller frames that can be processed faster, thus having the potential to affect engineering problems.


2 thoughts on “50-year-old problem solved!”

    1. Yes I’ve heard of him, but not a lot; he is definitely overlooked! What an inspiring man who shows that by perseverance and dedication we can achieve wonderful things! I’ve got to read up on him. Thank you for the link to the article!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s