Posted by
Microsoft Research Podcast
AI Frontiers: Models and Systems with Ece Kamar
Ece Kamar explores short-term mitigation techniques to make these models viable components of the AI systems that give them purpose and shares the long-term research questions that will help maximize their value.
That description will get no argument from Ravi Kannan, principal researcher in the Algorithms Research Group at Microsoft Research India.
“Nikhil Srivastava and his co-authors have settled an important, 54-year-old problem in mathematics,” Kannan says. “They gave an elegant proof of a conjecture that has implications for many areas of mathematics, computer science, and quantum physics.”
Srivastava offers a layman’s explanation of what he, Marcus, and Spielman have achieved.
“We proved a very fundamental and general statement about quadratic polynomials that was conjectured by [mathematician] Nik Weaver and that, he showed, implies Kadison-Singer. The proof is based on a new technique we developed, which we call the ‘method of interlacing families of polynomials.’”
The proof—for a more technical, extended discussion, see Srivastava’s post on the Windows on Theory blog—elicited the most basic of emotions from Srivastava when he got a chance to contemplate what he and his colleagues had wrought.
“My main reaction was awe at how beautiful the final proof was,” he recalls. “I actually started laughing when I realized that it worked. It 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.”
The Soul Physics site goes on to state, “Settling this conjecture shows an important way in which our experiments are enough to provide a complete description of a quantum system.”
Srivastava is in complete agreement.
“It has clear implications for the foundations of quantum physics,” he says. “This is something [theoretical physicist] Paul Dirac mistakenly thought was obvious, and Kadison and Singer and many other experts thought this was probably false.
“It implies that it is possible to ‘approximate’ a broad class of networks by networks with very few edges, which should have impact in combinatorics and algorithms. Finally, it is equivalent to several conjectures in signal processing and applied mathematics that seem to have practical use.”