Slashdot Mirror
How Computer Scientists Cracked a 50-Year-Old Math Problem (quantamagazine.org)
An anonymous reader writes: 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.
As a computer scientist, Daniel Spielman knew little of quantum mechanics or the Kadison-Singer problem's allied mathematical field, called C*-algebras. But when Gil Kalai, whose main institution is the Hebrew University of Jerusalem, described one of the problem's many equivalent formulations, Spielman realized that he himself might be in the perfect position to solve it. "It seemed so natural, so central to the kinds of things I think about," he said. "I thought, 'I've got to be able to prove that.'" He guessed that the problem might take him a few weeks.
Instead, it took him five years. In 2013, working with his postdoc Adam Marcus, now at Princeton University, and his graduate student Nikhil Srivastava, now at the University of California, Berkeley, Spielman finally succeeded. Word spread quickly through the mathematics community that one of the paramount problems in C*-algebras and a host of other fields had been solved by three outsiders — computer scientists who had barely a nodding acquaintance with the disciplines at the heart of the problem.
As a computer scientist, Daniel Spielman knew little of quantum mechanics or the Kadison-Singer problem's allied mathematical field, called C*-algebras. But when Gil Kalai, whose main institution is the Hebrew University of Jerusalem, described one of the problem's many equivalent formulations, Spielman realized that he himself might be in the perfect position to solve it. "It seemed so natural, so central to the kinds of things I think about," he said. "I thought, 'I've got to be able to prove that.'" He guessed that the problem might take him a few weeks.
Instead, it took him five years. In 2013, working with his postdoc Adam Marcus, now at Princeton University, and his graduate student Nikhil Srivastava, now at the University of California, Berkeley, Spielman finally succeeded. Word spread quickly through the mathematics community that one of the paramount problems in C*-algebras and a host of other fields had been solved by three outsiders — computer scientists who had barely a nodding acquaintance with the disciplines at the heart of the problem.
I don't even understand what's been solved!
They describe how. Five different, round-about ways of deriving positive intersecting matrices are described. They develop a method of defining boundary equations for the matrices, so as to prove an interesting algorithm that hadn't been able to be solved via an algorithm, just conjectures. They define this interesting boundary equation to box-in the conjectures, so to speak, and by defining the algorithmic domain, offer a proof that it works.
Profit!
I'm not sure how just yet.... but Profit!
If someone else can explain it succinctly, give it a shot.
---- Teach Peace. It's Cheaper Than War.
Kalai and Spielman are both very talented and have done a lot of work in many different branches of mathematics. Moreover, in this particular context they proved an equivalent version of the conjecture that was much closer to their own sort of work. The problem in question has many different equivalent formulations such as that described here http://arxiv.org/abs/math/0209078 is essentially a statement about vector spaces that anyone with some basic linear algebra background could understand. This is a very common tactic in mathematics if one has a tough problem: try to find equivalent problems that are in other subfields of math where their might be techniques to handle them.
This is old news, the proof was announced several years ago.
They use some cool theory initially developed by two Swedish mathematician, (one who sadly passed away a few years back),
dealing with polynomials and families of polynomials with only real roots.
The title "Mixed characteristic polynomials" has to do with matrices, and the characteristic polynomial of these.
A central concept is interlacing families of polynomials. Two polynomials with real roots are interlacing if the roots are interlacing, meaning when plotted on the real line, every other root belong to say the first polynomial.
It is actually pretty cool, since the original conjecture sounds really far from polynomials, matrices, and realrootednes.
What practical manifestations will this have?
Will it enable faster/better/bigger/smaller/higher/lower/longer/shorter/hotter/colder? What?
When Fascism comes to America, it will call itself Anti-Fascism, and tell you to give up your guns.
... Just file a bugzilla defect. We will fix it in the next release.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
Thanks, but that went way over my head, despite doing some pure maths at university. I'll wait for the xkcd version.
If you count being whisked away to dwell in an underground bunker "think tank" for your remaining years as "profit," then, yeah, these guys are in the cat-bird seat.
No one has a sense of humor anymore, especially when ti comes to algorithms proven by boundary equations.
---- Teach Peace. It's Cheaper Than War.
It comes down to the fact that some problems need outsiders, whose thinking have yet to be confined inside that proverbial box, in order to attain the correct solution
Muchas Gracias, Señor Edward Snowden !
What are you doing here? Where are your parents!?
Inheritance is the sincerest form of nepotism.
Those Mathematicians are just butthurt that some problems can "simply" be solved by enumeration. They are more then welcome to come up with an alternative proof.
Which is more important? The answer or the one of the solutions? Why "elegance of the proof" even matter?
"computer scientists who had barely a nodding acquaintance with the disciplines at the heart of the problem"
I don't think who wrote this has any idea how much math is in the university curriculum for computer science in different parts of the world. While far from "proper" mathematicians, there are lots of places where CS grads have much more than a nodding acquaintance.
I am putting myself to the fullest possible use, which is all I can think that any conscious entity can ever hope to do.
Programming, my boy, is to science what accounting is to calculus. I don't think you have even the beginning of a glimmer of understanding of what science is.
Not entirely true - I can assure you that, on a daily basis, I apply the scientific method to figuring out how to talk to undocumented "black boxes" (whether hardware, OS features, or just how to safely use buggy libraries I can't avoid or rewrite).
That said, your statement holds largely true in a bit different light than how you meant it...
In mathematics, you can spend a career mentally masturbating over your favorite "hard" problem, and retire after decades with nothing to show for it. In programming, if you work on a problem for five years, you'd damned well better get world-changing results, or find a new job.
It's important because they have tenure or are doing research as scholars for the given institutions. If someone working for Google, Apple or Microsoft comes up with something new or big on their time and dime, I'm sure they'd want their company to be mentioned as well. In research, you always mention your sponsor; may it be an academic institution or a particular grant you received.
I agree that for a given discovery, it's not because you are from Yale or Stanford that suddenly it's more valuable. Not every research from Yale of Stanford is per definition state-of-the-art. However, it's a chicken-egg problem, because these prestigious institutions tend to attract the brightest, or they at least get first pick in the pool of brightest people. This doesn't mean other researchers in other institutions can't be as good or even better.
I apply the scientific method to figuring out how to talk to undocumented "black boxes"
Don't we all :-) But I think that is not so much programming (ie writing program code) as it is intelligent planning before you make you next move.
In mathematics, you can spend a career mentally masturbating over your favorite "hard" problem, and retire after decades with nothing to show for it. In programming, if you work on a problem for five years, you'd damned well better get world-changing results, or find a new job.
Not really - universities do in fact require any scientist to be productive. Results don't have to be of the same order of magnitude as the achievements of Einstein, Gauss, Riemann etc. to be valuable. Lots of scientific research is farily humdrum, predictable stuff, that still has a very useful function. It is largely a myth that being a scientist is some sort of sinecure; and just because the general public can't see the point of it, doesn't mean that it isn't going to be important later.