Graph Isomorphism Algorithm Breaks 30-Year Impasse | Hacker News Reader

Graph Isomorphism Algorithm Breaks 30-Year Impasse

quantamagazine.org

222 pointskercker75 comments

Open articleView on HN

Graph Isomorphism in Quasipolynomial Time: http://arxiv.org/abs/1512.03547

Look at this asshole, having a finite Erdos number and publishing solo ;-)

Not just finite. One.

I think I understand the humor, but could you please explain so that I'm certain?

Your Erdos number is how many citation links you pass through to reach a paper by Erdos.

This author has (apparently) a nice tidy small Erdos number. To publish without co-authors denies those co-authors the chance to get (his Erdos number+1).

So clearly he/she is selfish and has the wrong priorities :)

FWIW, Babai (the author) has a very small Erdos number: 1:

http://www.ams.org/mathscinet-getitem?mr=584517

> Babai (the author) has a very small Erdos number

Let's quit beating around the bush: he has the smallest possible Erdős number[1]. If you don't presently have an Erdős number, or wish to improve your Erdős number for bragging rights, co-authoring a paper with him (or any anyone with an equivalent Erdős number) is the best possible outcome. (Obtaining an Erdős number of one is sadly no longer possible.)

[1]: https://en.wikipedia.org/wiki/Erd%C5%91s_number

Smallest possible for living humans. One person, notably, had a lower number, but he is no longer with us.

It's weird that you're downvoted. Just to clarify

> Paul Erdős has an Erdős number of zero.

My Erdos number is 30 milligrams.

Ahh! I didn't understand, but I do now. Thanks for the clarification! I totally grok how that could be "frustrating".

Also, don't miss the Erdős–Bacon number list. It sums one's Erdős number with the Keven Bacon number (shortest path to a movie with Keven Bacon). Some examples (Erdos + Bacon):

   Mit Math Professor Daniel Kreitman (1 + 2) = 3
   Richard Feynman (3 + 3) = 6
   NCAA gymnastics champion Kiralee Hayashi (3 + 2) = 5
   Natalie Portman (5 + 2) = 7

There's even a Erdos-Bacon-Sabbath number that also includes proximity to the band Black Sabbath.

Depending on how you count the Bacon number, I have an Erdős–Bacon number of 5 (2+3) and I'm actively working on my Sabbath number.

Previously posted and discussed extensively:

https://hn.algolia.com/?query=Graph%20Isomorphism&sort=byPop...

This article is worth discussing in itself, as it is very clear, gives a good sense of the situation, is easy to read and understand, and avoids the kinds of inaccuracy and solecism usually seen in articles about math.

Indeed. And the big news is that the paper is available today.

http://arxiv.org/abs/1512.03547v1

Indeed — and I upvoted the post. But a little bit of context might be handy.

> No one has ever found an efficient algorithm for an NP-complete problem, and most computer scientists believe no one ever will.

I find these kinds of assertions somewhat misleading. There _are_ "efficient" algorithms for, one could say, "pragmatic variations" of NP-complete problems. Some only work on some subset of cases (perhaps most of the useful ones), or non-deterministic (but you run them enough times and get the right answer), etc.

This. MJD has a great bit on blanket statements about "NP-complete means hard":

    http://perl.plover.com/yak/12views/samples/notes.html#sl-24

Basically, you can often either settle for slightly suboptimal solutions, or ignore a few pathological worst cases. That said, I suspect that P != NP, and thought this was a good article.

Ok so the question is, while theoretically this is an important work, is it really worthy having a practical implementation?

(I remember something similar happening with "Primality testing is P" but the existing, non-P algorithms were good enough so people wouldn't bother using it except in specific situations)

No. As the author notes in the preprint, there are already numerous very fast, practical algorithms. This one is only asymptotically faster, and by itself it would probably be slower in real-world applications.

If it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time.

The claims you're making in this subthread are not precise enough to be correct. If you only allow a constant finite amount of time to solve a given problem, then aysmptotics guarantee nothing. An O(1) time could solve fewer instances than an O(2^2^n) time algorithm. It is also not true that the asymptotically faster algorithm "can solve more instances as the allocated time increases." These statements are only true if you add the phrase "sufficiently large" to them. So asymptotically faster algorithms can solve more instances as the allocated time bound increases, provided that the time bound is sufficiently large. But how large that "sufficiently large" needs to be is arbitrary, so you can't say that Babai's algorithm is practical without either precisely studying the constants involved in the algorithm (which Babai did to some extent, but omitted in the notation for clarity), or doing empirical analysis, which is unlikely to ever happen with Babai's algorithm.

The statement is correct.

"Sufficiently large" is implied and also not strictly necessary for the statement to be correct.

If it's not required then it's not implied, and unfortunately it is required. If you want to keep having serious discussions about this stuff I suggest you go read some more about algorithms.

You should be able to simply state the error in my statement then. Anyway, others disagree with you.

Yeah, but the question is does the new algorithm beat the old ones for problems that are solvable in reasonable time. A constant time algorithm is not that useful if the constant happens to be 10^1000 years.

I don't think this claims to be a constant time algorithm.

Can someone rule out that there are no problem instances that this algorithm can solve in a reasonable time that others cannot?

Reread my comment, I'm not saying that it's a constant time algorithm, I'm saying that even constant time algorithms can be impractical.

Reread my comment.

If the paper is correct then there ARE problems that this algorithm can solve in less time than others. But it may be that every problem on which it is faster requires more bits of memory than there are atoms in the universe. Or that every problem on which it is faster would have a runtime that is 10^100 times the lifetime of the universe.

Any of those things could be the case. I'd modify your second sentence to say known atoms in the universe, and the second: projected lifetime.

Do you know if the paper (or any commentary) addresses these concerns?

> If it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time.

More precisely, there are problems that the asymptotically faster one can solve in less time than the asymptotically slower one, or, equivalently, there exists some time period at and beyond which the asymptotically faster algorithm can solve problems that cannot be solved by the asymptotically slower one in the same time.

However, the minimum time period where that becomes true with real implementations running on real, available hardware may be very large, so there may not be any practical advantages to an asymptotically faster algorithm.

Agreed. One would need to actually present actual implementations to compare.

It may not be the case in our universe. An O(n^2) algorithm is only faster than O(n^3) algorithm for an n > N (N may be 0). N may be so large that the problems it solves faster take more time than the heat death of the universe.

I'm not sure I understand what you're saying. The class of problems Babai's algorithm can solve is exactly the same as the problems any other of the algorithms can solve. They're all asymptotically bounded in time, as well.

If you have a finite amount of time, a given algorithm will only be able to solve a subset of all problem instances in the allocated time (assuming an infinite set of problem instances). If you have two algorithms and give the same finite amount of time to each, the asymptotically faster one would be expected to be able to solve more and/or larger problem instances in the allocated time than the asymptotically slower algorithm, as your allocated time increases.

It is important to note that big o notation is not a measure of "how fast will it take". It is not a measure of time at all, but a matter of how many discrete steps are required to solved the problem as a function of input size. Each step could take longer, which could effectively give it a longer run time. Solvability by the algorithm and the big O notation assumes unlimited time. They are all " theoretically solvable". The constant time and size of N would determine which implementation would be practically faster in a given situation. Lower asymptotic bounds algorithms are faster, given a sufficiently large (and specific) N. But that depends on the implementations. It may be that N is larger than most GI problems compared to the programs that currently run. The current algorithms run in polynomial time for most graphs (just like many sorting algorithms run closer to n rather than n log n the closer you get to pre-sorted input)

If the finite time is smallish, and the constant factor in the asymptotically faster algorithm is sufficiently large, it might be the case that it can't solve any instances of the problem in that time.

The algorithm is only of theoretical interest, the situation is similar to primality testing. In practice programs such as nauty are good enough.

He said in the talk, answering this exact question, that basically his result shows that there aren't any really hard cases for the heuristic algorithms to run into. It would of course require some analysis to connect them to his result, but there would be no point in implementing his algorithm on a computer.

Is somebody able to explain in more detail what the "Greater metropolitan area" of P space means? I have a CS undergrad degree so I get what polynomial space is, just not sure about the quasi-p-space part.

Quasi-polynomial time is slower than polynomial time, but (much) faster than exponential time. Basically, if polynomial is O(n^c) and exponential is O(c^n), then quasi-polynomial is O(x^(log(n)^c); that is, n does show up in the exponent, but it's some power of the log of n.

In theoretical terms, it's much closer to a polynomial problem than an exponential one.

Gotcha, that makes perfect sense, thanks for the explanation!

A quasi-polynomial time algorithm is one which has a worst case running time of 2^[O((log n)^c)], for some fixed constant 'c'. Polynomial time (PTIME) algorithms are a special case (where c=1).

"Greater metropolitan area" is a way of saying that Babai's proposed algorithm while not exactly in PTIME, is still very close. Indeed, in a certain sense it is now "closer" to PTIME than EXPTIME.

Thanks!

I very nearly took Algorithms from this guy. Toughest professor (and grader) in the CS program, by far. He's quite a character, though.

What happens with this one ?

Polynomial Time Algorithm for Graph Isomorphism Testing. http://mt2.comtv.ru/

Is this a hoax or has some substance ?

Earlier version was wrong https://cstheory.stackexchange.com/questions/1064/polynomial..., I doubt the current version has any substance.

How long until we start seeing this algorithm in Google interviews?

Very long, most CS people don't know any group theory.

Just a week or two ago I saw someone get downvoted for suggesting that many CS degrees don't include real analysis. I suspect that by now undergrad CS programs are all over the place, and I wouldn't dare make broad generalizations about the math content of a CS degree anymore.

I am pretty sure that most CS students don't have the algebra background to understand what's going on in this algorithm. I've taken a year's worth of algebra and the algorithm still relies on stuff that I don't get.

Edit: and most CS programs do not emphasize traditional math anyways. No analysis, some linear algebra, very very little abstract algebra, and that's pretty much it.

I would, because I'm on the inside. There are even many CS degrees that don't require a course in algorithms. You have to remember that most CS degrees come from public/state universities, not Stanford and MIT. And CS students at public/state universities are largely mathphobic.

That's a very broad generalization. There are many public/state universities with amazing CS research and programs (e.g. UC Berkeley) that are very math-heavy.

As a student at UC Berkeley, students need to study at most linear algebra and multivariablr calc to major in CS/EECS.

No Boolean algebra, probability, or statistics?

>There are even many CS degrees that don't require a course in algorithms.

What CS degree doesn't require a course in algorithms? I assume there are some Software Engineering degrees that don't, but how can you spend 4 years studying computer science without an algorithms course?

>And CS students at public/state universities are largely mathphobic.

I agree that most CS students try to avoid relatively proof heavy classes like Automata. But almost all CS courses require up to Calc 2 and discrete math, so I'm sure the truly "mathphobic" students would have majored in CIS or something else.

I also don't think this has anything to do with Standford MIT vs public universities. Students at those Universities would avoid elective proof heavy classes as well. I did undergrad at a relatively unknown state school, and now I'm in grad school in a top ten program. I know plenty of people from both schools who avoid rigorous proof heavy classes when they can.

Here is one such program, North Carolina State University, which requires a basic theory course (automata) but no algorithms course.

https://www.csc.ncsu.edu/academics/undergrad/semester.php

There are many more X state universities that churn out computer science degrees than the top schools.

CSC 316 appears to be the main algorithms course (recommended 4th semester course).

Pretty big generalization there. There are 20+ CSU's and 10 UC's in California. You really going to paint 30 schools with such broad strokes in one state alone, plus the rest of the US?

Most CS programs that I am aware of don't require real analysis. I know Berkeley EECS doesn't, and it's a very rigorous program. Stanford too.

I plan on taking it, but only because it shows up in a few esoteric theoretical machine learning contexts.

My father got a BA in CS that didn't even require calculus. He graduated in the 90s.

Too true, it's one of the reasons why I did a Maths degree to complement my Comp Sci degree.

is that all it's good for?

Nope, it's got useful applications in the real world in, say, chemical compound databases.

This algorithm in its current state really doesn't; GI for most natural instances was already being solved quickly via some heuristics.

This algorithm proves a quasipolynomial upper bound on the complexity of GI.

Er, perhaps.

InChI is already based on nAUTy, which even this work acknowledges as the fastest general approach (except for saucy, bliss, etc).

So there are no implications of László Babai that have an impact on chemistry, AFAICT.

Thanks for posting this. In the future, could you please add the algorithm to the title? This feels a couple steps removed from clickbait. No offense intended; it's just a suggestion.

> Babai has declined to speak to the press, writing in an email: “The integrity of science requires that new results be subjected to thorough review by expert colleagues before the results are publicized in the media.”

Quoth the media ... Apparently unironically.

I'm okay with Quanta Magazine leaving out the irony; I can imagine the Engadgets and Buzzfeeds of the world would omit his response and draw their own wild conclusions regardless.

"Top 10 ways your graphs may be isomorphic. Results will surprise you!!"

"We would like to explain how; but the proof is too long to be tweeted within the 144 character limit!"

For the nearly all practical purposes, there already exist efficient algorithms for GI. This work is mostly of interest for theoretical matters because it shows that GI can be solved in quasi-poly time for _all_ graphs, whereas previous work still had exponential time worst-cases. Hence why there isn't really a concise algorithm that you'd want to implement.

It's not clickbait, it just requires reading the article for the full story.

I also recommend this blog post: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algor...

Reply on news.ycombinator.com