Graph Isomorphism update: quasipolynomial claim restored | Hacker News Reader

Graph Isomorphism update: quasipolynomial claim restored

people.cs.uchicago.edu

200 pointstejtm35 comments

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.

I 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.

Even 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.)

I 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.

Graph 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.

Wiles' 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.

And that doesn't even make it unusual. Most mathematical results are first presented at conferences or workshops, sometimes long before publication.

I was around at the time. I remember the buzz after day one of his two day workshop. Everyone knew where he was going.

Wiles 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.

Saying you’re working on FLT in the late 20th century is a good way to make everyone think you’ve gone nuts and are wasting your time. It makes some sense to make sure you have something solid before you mention it.

Technically he was working on the Taniyama conjecture (now known as the modularity theorem), not on Fermat's last theorem.

or conversely, if they believe you, they could try to sniff your approach and take the credit for it. given the fame of FLT I dont blame him for doing it undercover.

If only the ABC conjecture proof was handled as transparently.

What 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.

What 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.

I 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.

On 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.

I 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.

I don't know this work, about I appreciate the candor and honesty this academic presents. Thanks for posting.

Great 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"!

Babai 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.

Makes me wish it was possible to write a -8 page paper. :)

I would have written a shorter letter, but I did not have the time. - Blaise Pascal, Provincial Letters: Letter XVI (4 December 1656)

Just write an 8 page paper on antimatter [pun intended].

This is so cool, the guy (among other things) beat an important algorithm that had stood as the fastest for decades.

Luks worked together with Babai on the previous fastest algorithm. Babai is just very modest when he only mentions Luks when reffering to it.

It 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 The seminar is broadcast live on youtube, notes and video are available afterwards.

It's the retraction of the retraction, basically

Not 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.

Does this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?

I don't think bitcoin's work function is based on graph isomorphism?

Yeah, 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.

And finding a nonce that makes the block have a SHA256 with many leading zeroes is probably not an NP-hard problem.

It is, some people also tried SAT solvers for mining:

http://jheusser.github.io/2013/02/03/satcoin.html

Please 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.

Not even related.

Reply on news.ycombinator.com