Sign In

Communications of the ACM

ACM News

‘outsiders’ Crack 50-Year-Old Math Problem


Developing a plan for network sparsification.

Addressing a question that "defied the best efforts of some of the most talented mathematicians of the last 50 years."

Credit: Alessandro Gotardo

In 2008, Daniel Spielman told his Yale University colleague Gil Kalai about a computer science problem he was working on, concerning how to "sparsify" a network so that it has fewer connections between nodes but still preserves the essential features of the original network.

Network sparsification has applications in data compression and efficient computation, but Spielman’s particular problem suggested something different to Kalai. It seemed connected to the famous Kadison-Singer problem, a question about the foundations of quantum physics that had remained unsolved for almost 50 years.

Over the decades, the Kadison-Singer problem had wormed its way into a dozen distant areas of mathematics and engineering, but no one seemed to be able to crack it. The question "defied the best efforts of some of the most talented mathematicians of the last 50 years," wrote Peter Casazza and Janet Tremain of the University of Missouri in Columbia, in a 2014 survey article.

 

From Quanta Magazine
View Full Article

 


 

No entries found