How Computer Scientists Cracked a 50-Year-Old Math Problem (quantamagazine.org) 96
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.
Cracked? Let me guess (Score:1, Funny)
By injecting its SQL
It probably comes down to ... (Score:2)
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
Re:It probably comes down to ... (Score:4, Interesting)
Indeed. That is why I am interested in different schools of thought in mathematics. For example, the ancient Greeks were builders rather than mathematicians, and therefore solved different problems or similar problems in another way. I would not know how to prove Pythagoras' theorem without the Greek school of thought. On the other hand, the Arabic school of thought brought us abstract thinking. It took aerodynamics to add boundary layer theory to computational mathematics.
The most interesting thing can occur when those schools of thought are mixed. Hodographic transformation as used in aerodynamics is very similar to a Burrows-Wheeler transform in computer science, but the application is totally different. Who knows what other differential equations solving techniques could yield better data compression, for example?
Re:It probably comes down to ... (Score:5, Funny)
The difference in the way of thinking is simple.
Mathematician: "This is too complex for my brain. I can grasp the outer layer of the problem, but the underlying thing is beyond any human's capacity."
CompSci guy: "Oh, I can write a program that handles the outer layer of this problem; I have no clue what that underlying thing is but I bet it can be brute-forced."
Re: (Score:2)
Daniel Spielman, aka Little Bobby Tables, has solved....
Re: (Score:2)
Output of sudo apt-get moo maybe was the inspiration? See:
http://paste.ubuntu.com/135042... [ubuntu.com]
Unless it's fortune | cowsay or something. See:
http://paste.ubuntu.com/135042... [ubuntu.com]
Given the relevance, often oblique, I'm inclined to believe this is manually done. I've not seen it mentioned on Slashdot's hidden thread.
Whoosh over my head (Score:5, Insightful)
I don't even understand what's been solved!
Re: (Score:2, Insightful)
I don't even understand what's been solved!
The answer was 42, so no worries.
Re:Whoosh over my head (Score:4, Insightful)
I don't even understand what's been solved!
I don't either, but it's worth noting that this is an utterly shit submission; not only does it not give us any clues as to even what kind of problem might have been solved, but there's no informative link which is kind of what the web is all about.
Re: (Score:2)
I won't even begin to claim to understand it ... but here's the wikipedia [wikipedia.org] link for those of us who need a high level explanation of it.
Admittedly, I could use a "dance your PhD"/crayola explanation of this.
Even the wiki article is way over my head too.
Great Title (Score:1)
"How Computer Scientists Cracked a 50-Year Old Math Problem". Great! How?
Re:Great Title (Score:5, Interesting)
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.
Re: (Score:3)
Thanks, but that went way over my head, despite doing some pure maths at university. I'll wait for the xkcd version.
Re: (Score:3)
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.
Re:Great Title (Score:5, Funny)
No one has a sense of humor anymore, especially when ti comes to algorithms proven by boundary equations.
Re: (Score:2)
That's not true. Just yesterday, I began a joke with "N people walked into a bar, where N is an integer greater than 1 and less than 3." The audience was in stitches!
Re: (Score:2)
Interesting...
Now explain it to me like I'm five.
Re:Great Title (Score:4, Funny)
Re: (Score:2)
These nice math people solved a big problem! People had tried to figure it out for gosh, fifty years! Then they did it. The problem was like if you had lots of apple orchards, each with different apples. Birds would fly over and poop on them sometimes. You wanted to find out which birds were pooping on what trees and also which apples on which branches were clean, and all this, over a period of time in which orchards. Tough, huh?
Re: (Score:2)
It might be the DMT kicking in.
Those who can, program. (Score:1)
Re: (Score:2)
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.
Re: (Score:3)
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 m
Re: (Score:3)
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 o
Re: (Score:2)
I'm a professional developer with a post-grad degree in Mathematics.
There's an ounce of truth in what he says, not the part about computer scientists or software engineers somehow being better than scientists, on the contrary, you're largely right because most programmers decry maths and claim it doesn't matter to them, but they're really just the dross of the industry. Maths is what separates someone reinventing the wheel by condemning themselves to produce CRUD applications for all eternity from someone w
Re: (Score:1)
... to AI solutions like Siri.
Good lord, don't use Siri as a shining example of "novel"!!! Use Deep Blue or Watson!
You're giving AI a bad name using Siri as an example!
Re: (Score:2)
I don't think you have even the beginning of a glimmer of understanding of what science is.
Having worked with physicists, you'll forgive me that I'm not really impressed? It's just a job for lots of physicists, and they're good in varying degrees. The best do a bit of programming, but most just used the libraries we programmed for them.
Spielman is hardly ab outsider (Score:5, Informative)
Re: (Score:2)
She decided to stay home with the kids and not have a career.
Some info (Score:5, Informative)
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.
Layman Terms Please (Score:3, Insightful)
What practical manifestations will this have?
Will it enable faster/better/bigger/smaller/higher/lower/longer/shorter/hotter/colder? What?
Re:Layman Terms Please (Score:5, Funny)
Dude, we get the first story reminiscent of the Old Slashdot in freaking forever... and you're asking for practical applications?
Re: (Score:2, Funny)
I'd like a car analogy.
Re: (Score:2)
I'd like a car analogy.
It's as if a motorcycle mechanic had figured out how to replace the burnt out engine of a unimog with a new crated engine in record time by using engine hoist techniques usually reserved for motorcycles and not cars.
Re: (Score:2)
It relates to quantum theory. Maybe putting boundaries on various solutions. I wonder if it's related to the discovery that there are bundles or hairs of dark matter around every planet in the Solar system.
Re: (Score:2)
They use some cool theory initially developed by two Swedish mathematician, (one who sadly passed away a few years back),
I've yet to meet someone who happily passed away.
If you find holes in the proof ... (Score:3)
Differing perspectives (Score:2)
To paraphrase a popular programming axiom:
"There's more than one way to think of it"
Math physics, etc. is our own physically limited observation and description of how math and the universe functions, doesn’t mean it's the correct way or able to get achieve all the answers, Kind of like Einstein, Tesla, and many other discoverers, its not always thinking the ways everyone else has been taught to think but coming at it from a wholly different perspective... and not always by such seemingly brilliant in
OK, so he's a lot smarter than I am... (Score:2)
[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.
I've underestimated ever-so-slightly like that. Now I don't feel so bad about being dumb!
Re: (Score:2)
... He guessed that the problem might take him a few weeks. Instead, it took him five years.
I've underestimated ever-so-slightly like that. Now I don't feel so bad about being dumb!
It's on-spec (he delivered the proof all right) and on-budget (not sure about academia, but he still has a paid job, doesn't he?), so it was bound to be the schedule that had to budge [wikipedia.org].... That's the problem with giving jobs like this to IT people :-)
Name drop (Score:2, Insightful)
Can we please try to name drop some more schools into the teaser?
I am SURE somewhere we missed somebody's school affiliation that, while having jack shit to do with anything, merits a mention. Surely a janitor who attended night classes at Yale Lock Academy or somebody's third cousin Louis who once had cheese from a shop near Rutgers deserves the same accolades.
Seriously, why the hell does it matter where all these people went to school and why does this need to be in the teaser? You know what was MISSING
Re: (Score:3)
I agree that for a given discovery, it's not because you are from Yale or Stanford that suddenly it's more valuable. Not ever
Re: (Score:3)
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?
What an IRRITATING article! (Score:2)
It doesn't say *anything* about the conjecture in the first place! You read on and on and on. You hope that at one point the vapid author comes close to describing what the problem they solved was all about and every time. Every. Single. Time. The author manages to deflect away from it. Bah!
Ridiculous final claim. (Score:1)
" computer scientists who had barely a nodding acquaintance with the disciplines at the heart of the problem."
If it took 5 years and actually worked it's because they were becoming very, very well acquainted with disciplines at the heart of the problem.
Re: (Score:1)
Sort of. If it took 5 years and actually worked they were clearly becoming very, very well acquainted with a heart of the problem. (I do mean "a" heart: there can be more than one way of dealing with a complex problem.)
Whether they were becoming very, very well acquainted with disciplines at the heart of the problem is another question.
For example in perturbation theory (examining what happens to a system if you change a parameter by a small amount) there are objects called Canards. These were first di
barely a nodding acquaintance (Score:3)
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.
Annoying summary (Score:1)
I think people who write summaries that do not contain the most important piece of information should be killed.
A sentence describing the problem and a sentence describing the breakthrough would be great. Not a life story about some people I care nothing about.
I think this will be increasingly common (Score:2)
Math is a huge subject. I've heard most mathematicians can't read most mathematics papers. I believe we will increasingly see math problems solved by people who see new isomorphisms; people who realize that two problems in two fields are actually the same problem. I'm just waiting for the day that an important math problem is discovered to have been solved long ago in a different formulation.
Do people do this in their spare time? (Score:2)
I mean, are these guys working on this between Star Wars Battlefront matches, or when they get burned out collecting items in Fallout 4? I mean, 15 years is a long time, so there had to be some sort of routine to this, right? What about when Everquest was popular, did that push this out for an extra five years or what?