Nikhil Srivastava, a mathematician at Microsoft Research, India, has been declared the joint winner of the prestigious George Polya Prize for solving the Kadison Singer problem, which has eluded mathematicians for about 50 years. He shares the prize with Adam W. Marcus and Dan A. Spielman from Yale University, U.S.
In an email, he described the problem and his plans.
How do you feel about winning the Polya Prize for mathematics?
I feel pretty good. Our work has been quite well-received, but I didn’t expect anything in particular.
Can you tell us about the collaboration?
My collaborators are Adam Marcus and Dan Spielman (the latter was my PhD advisor). We were together at Yale for two years when we started working on this and then I graduated while Adam stayed back for another two [years]. During this time we met sporadically, but mostly I collaborated with the other two over email. This was very effective during the last year, probably in part because we already knew each other well. I actually enjoy this mode of collaboration a lot, in which you think hard by yourself for a week or so at a time, and then carefully write up what you find before sending it; I actually like this pace, which is quite different from meeting regularly.
In simple terms, what is the Kadison Singer problem and how is it connected to quantum mechanics?
The Kadison-Singer problem arises from the question of how to describe, i.e., parameterize, the states of a quantum system. For example the state of an electron in a hydrogen atom can be described completely in terms of four quantum numbers — n, l, m and s (energy, angular momentum, magnetic, spin). Since quantum mechanics is formulated in the language of linear algebra, the question of whether or not this is mathematically possible for a general quantum system boils down to certain questions about infinite dimensional matrices.
Kadison and Singer asked one such question, whose resolution implies it is indeed possible in a wide variety of situations. Note that this is a mathematical question (about the properties of the linear-algebraic formalism used to describe quantum mechanics) and not a physical question (about reality).
How does this relate to questions on networks?
The original question about infinite matrices was reduced by Anderson to certain questions about finite matrices. Specifically, whether all finite matrices of a certain type can be partitioned ‘evenly’ into two ‘balanced’ pieces. Since every finite network can also be represented as a matrix, this translates naturally into a question about partitioning networks into ‘balanced’ parts.
Some applications of the result?
It resolves a mathematical issue with a widely used formalism for quantum mechanics (although this is not an issue that actual physicists, who largely consider it a technicality, were concerned about). It also tells us new things about properties of networks, as well as certain schemes for transmitting information robustly. Basically, since lots of different objects can be encoded as matrices, it has the potential to shed light on many areas.
What is your plan for the future?
I plan to keep doing research in computer science and mathematics. One of the main questions is to understand this proof in the context of some larger theory, which explains exactly when the phenomena that we exploit occur. Another more practical question is to find an efficient algorithm which produces the partitions that our theorem guarantees; this would probably have applications in computer science.
What other problems are you interested in?
I am interested in finding more efficient ways of doing computation on networks, and in finding new ways to view them, perhaps inspired by physics. I am also getting interested in quantum mechanics and quantum computation, though I do not have any specific projects in those areas right now.
Solving the problem was great. The solution is beautiful. It is the sort of thing that when you see it you start smiling. When I gave talks on this work, there would often be people in the audience smiling. I think they were smiling because they thought it was beautiful, too. Sharing that experience with someone feels amazing. I think that's really cool.