6 ms·
Graph Isomorphism update: quasipolynomial claim restored
This is _NOT_ the retraction update of several days ago.
http://people.cs.uchicago.edu/~laci/update.html
previous posts to same link are for the retraction so unable to just link directly as they take precedence.
- raverbashing 10y agoIt's the retraction of the retraction, basically
- oh_sigh 10y agoNot exactly - Helfgott's initial analysis pointing out the flaw was(and still is) correct - it's just that Babai found a way to work around it.
- jwtadvice 10y agoI remember the same thing originally happened with Wile's proof of FLT. It's heartwarming to know that scholars continue to skeptically check each other's work for factual correctness.
- williamstein 10y agoEven better -- this situation is much more public and open than the situation with Andrew's FLT proof. I remember when Wiles proof was announced, when there was a gap, etc. only a select few got to actually look at the proof. It was only published after it had been very carefully checked. I started studying number theory exactly during this strange period of secrecy in 1993. Incidentally, exactly at that time, I used to play around writing computer games with Harald Helfgott, who is the guy who just found the mistake with Graph Isomorphism a few days ago... (He's a fantastic mathematician.)
- saalweachter 10y agoI can't help but wonder if the qualitative difference in the problems -- graph isomorphism is an important, active area of applied mathematical research in search of a better algorithm, FLT was a multi-century abstract mathematical puzzler -- makes for a difference in the groups of people working on the problems and their attitudes.
- Jweb_Guru 10y agoGraph isomorphism isn't that important practically (subgraph isomorphism is, but it's NP-complete and, IIRC, APX-hard as well) and the hard graph cases don't come up much in practice (despite being a relatively large percentage of random graphs, AFAIK). I think it reflects a difference in how mathematics is done; the quasipolynomial result was first presented at a conference, not in a paper, which definitely wouldn't have been the case 20 years ago.
- mafribe 10y agoWiles' original FLT result was first presented at a workshop in Cambridge, although he didn't explicitly state that he had succeeded (sans the gap) in proving FLT, he left that for the audience to infer.
- tacomonstrous 10y agoAnd that doesn't even make it unusual. Most mathematical results are first presented at conferences or workshops, sometimes long before publication.
- moomin 10y agoI was around at the time. I remember the buzz after day one of his two day workshop. Everyone knew where he was going.
- JCzynski 10y agoWiles was weird at the time. Math is done in public, he just really wanted to be the one to have the final valid proof of Fermat's Last Theorem.
- cromwellian 10y agoIf only the ABC conjecture proof was handled as transparently.
- aalireza 10y agoWhat you're saying implies that a situation is -even- theoretically possible such that a radically new mathematical theory with near-completely novel underlying frameworks that's essentially developed by a single guy over the span of almost a decade that necessarily resulted in a deviation from the route focused by the majority of researchers, could be `quickly` understood/vetted by other mathematicians via traditional methods of un-automated peer-review process. I guess if that was true, we would have been a significantly smarter species, or at a the very least, had god-like context-switching or learning abilities.
- cromwellian 10y agoWhat I meant is, the author of the theory for a long time refused to travel and present his theory in person to walk others through it. Things might have gone faster if the author had taken the time to teach others and help them understand it.
- stablemap 10y agoI want to point out two more differences: in Wiles's case it took about a year of work with Richard Taylor to patch things up.
- tacomonstrous 10y agoOn the other hand, Wiles's work was quite a bit more complex conceptually just in terms of the sheer number of moving pieces involved, though the level of cleverness required is probably comparable in the two cases.
- CJefferson 10y agoI don't think this is finished yet. The paper is very complex, and not completely checked yet. Other issues will possibly arise. That's part of any large maths proof.
- tomrod 10y agoI don't know this work, about I appreciate the candor and honesty this academic presents. Thanks for posting.
- WhitneyLand 10y agoThis is so cool, the guy (among other things) beat an important algorithm that had stood as the fastest for decades.
- wolfgke 10y agoLuks worked together with Babai on the previous fastest algorithm. Babai is just very modest when he only mentions Luks when reffering to it.
- masalax 10y agoGreat news! >I am working on an updated arXiv posting. I sure hope this isn't the new "I have discovered a truly marvelous proof of this, which this margin is too narrow to contain"!
- cvoss 10y agoBabai commented that the new work-around requires a 2-page proof and makes 10 existing pages obsolete. So, a net savings of 8 pages, in theory! We'll see how it turns out.
- xiphias 10y agoDoes this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?
- drdeca 10y agoI don't think bitcoin's work function is based on graph isomorphism?
- xiphias 10y agoYeah, I read more about it, only subgraph isomorphism is known to be NP-complete...of course the complexity of that will remain a mystery for a long time.
- wolfgke 10y agoAnd finding a nonce that makes the block have a SHA256 with many leading zeroes is probably not an NP-hard problem.
- xiphias 10y agoIt is, some people also tried SAT solvers for mining: http://jheusser.github.io/2013/02/03/satcoin.html http://jheusser.github.io/2013/02/03/satcoin.html
- wolfgke 10y agoPlease look up the definition of NP-hardness again. If the problem (#) := "finding a nonce that makes the block have a SHA256 with many leading zeroes" was NP-hard, it would be an interesting idea to use a solver for (#) to solve e.g. SAT (not the other way round!). TLDR: You talked about the wrong inclusion.
- ajkjk 10y agoNot even related.
- deleted 10y ago[deleted]
- heinrichf 10y agoIt should be noted that Helfgott (who found the issue in the proof) is scheduled to talk about Babai's work at the famous Bourbaki seminar next saturday: http://www.bourbaki.ens.fr/seminaires/2017/Prog_janv17.html http://www.bourbaki.ens.fr/seminaires/2017/Prog_janv17.html The seminar is broadcast live on youtube, notes and video are available afterwards.