16 ms·
Graph Isomorphism Algorithm Breaks 30-Year Impasse
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- gre 11y agoGraph Isomorphism in Quasipolynomial Time: http://arxiv.org/abs/1512.03547 http://arxiv.org/abs/1512.03547
- jgn 11y agoThanks 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.
- tragic 11y ago> 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.
- grrowl 11y agoI'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.
- kzrdude 11y agoIt'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-algorithm-for-graph-isomorphism-the-details/ http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algor...
- riscy 11y agoFor 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.
- kzhahou 11y ago"Top 10 ways your graphs may be isomorphic. Results will surprise you!!"
- williamjennings 11y ago"We would like to explain how; but the proof is too long to be tweeted within the 144 character limit!"
- nine_k 11y agoPreviously posted and discussed extensively: https://hn.algolia.com/?query=Graph%20Isomorphism&sort=byPopularity&prefix&page=0&dateRange=all&type=story https://hn.algolia.com/?query=Graph%20Isomorphism&sort=byPop...
- pervycreeper 11y agoThis 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.
- Zach_the_Lizard 11y agoHow long until we start seeing this algorithm in Google interviews?
- Ar-Curunir 11y agoVery long, most CS people don't know any group theory.
- wtallis 11y agoJust 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.
- Ar-Curunir 11y agoI 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.
- Zach_the_Lizard 11y agoMy father got a BA in CS that didn't even require calculus. He graduated in the 90s.
- j2kun 11y agoI 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.
- pm90 11y ago
- onetwotree 11y agoLook at this asshole, having a finite Erdos number and publishing solo ;-)
- fapjacks 11y agoI think I understand the humor, but could you please explain so that I'm certain?
- ergothus 11y agoYour 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 :)
- fapjacks 11y agoAhh! I didn't understand, but I do now. Thanks for the clarification! I totally grok how that could be "frustrating".
- s-phi-nl 11y agoFWIW, Babai (the author) has a very small Erdos number: 1: http://www.ams.org/mathscinet-getitem?mr=584517 http://www.ams.org/mathscinet-getitem?mr=584517
- deathanatos 11y ago> 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 https://en.wikipedia.org/wiki/Erd%C5%91s_number
- LesZedCB 11y agoIs 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.
- apetresc 11y agoQuasi-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.
- LesZedCB 11y agoGotcha, that makes perfect sense, thanks for the explanation!
- anuragbiyani 11y agoA 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.
- LesZedCB 11y agoThanks!
- raverbashing 11y agoOk 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)
- sold 11y agoThe algorithm is only of theoretical interest, the situation is similar to primality testing. In practice programs such as nauty are good enough.
- kachnuv_ocasek 11y agoNo. 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.
- jsprogrammer 11y agoIf it is asymptotically faster, then it is implied that there are problems the faster one can solve, that the other cannot, assuming finite time.
- kachnuv_ocasek 11y agoI'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.
- jsprogrammer 11y agoIf 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.
- Devid2014 11y agoWhat happens with this one ? Polynomial Time Algorithm for Graph Isomorphism Testing. http://mt2.comtv.ru/ http://mt2.comtv.ru/ Is this a hoax or has some substance ?
- sold 11y agoEarlier version was wrong https://cstheory.stackexchange.com/questions/1064/polynomial-time-algorithm-for-graph-isomorphism-testing https://cstheory.stackexchange.com/questions/1064/polynomial..., I doubt the current version has any substance.
- superuser2 11y agoI very nearly took Algorithms from this guy. Toughest professor (and grader) in the CS program, by far. He's quite a character, though.
- dcohenp 11y ago> 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.
- username223 11y agoThis. 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.