László Babai
2015 · arXiv
We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial ($\exp((\log n)^{O(1)})$) time. The best previous bound for GI was $\exp(O(\sqrt{n\log n}))$, where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp(\tilde{O}(\sqrt{n}))$, where $n$ is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism φ that maps a given permutation group $G$ onto $S_k$ or $A_k$, the symmetric or alternating group of degree $k$, where $k$ is not too small. We say that an element $x$ in the permutation domain on which $G$ acts is affected by φ if the φ-image of the stabilizer of $x$ does not contain $A_k$. The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
3 selected excerpts · 3 total mentions
It's now a _solved_ problem - both theoretically (with Babai et al's paper a few years ago) and practically (with nAUTy/Bliss, and similar software). Not sure what the key paper is, but "Graph isomorphism in quasipolynomial time" is at leas relevant: https://dl.acm.org/doi/10.1145/2897518.2897542 or perhaps, this arxiv paper: https://arxiv.org/abs/1512.03547 No idea about a quantum algorithm for GI
https://arxiv.org/abs/1512.03547 Note it was actually Quasipolynomial time, not true polynomial time. It's also a pretty recent paper, so it could turn out to have flaws.
That's a classic motte-and-bailey doctrine right there. It shows Taleb commenting on a topic he clearly knows nothing about while presenting himself as an expert. Something, if I recall correctly, he often criticises in other people. And it's not merely being imprecise, it's at least halfway between being wrong and not even wrong. If someone's that sloppy on Twitter, why would their research be any better? It probably isn't. In a series of tweets posted around the same time, Taleb also pointed to a "technical" paper claiming a connection between P versus NP and the effects of GMOs [1]. It's drivel. A series of non-sequiturs. No connection is actually established, only…
claimed. I credit that paper only with relieving me of the dilemma of whether Taleb is an interesting thinker or just another crackpot. (And I'm not even a GMO enthusiast.) The tweets are now gone; I only found this archive.is link because it was posted to a mathematics cranks subreddit. Probably because these were too obvious of an embarrassment to him. Fine. Though I think Taleb also likes to talk about "courage" a lot... Taleb's other "technical" papers are not particularly impressive either. I find them completely inscrutable; Taleb never explains his notation or terminology, and I often have a hard time deciphering equations he writes. While this may be because of my rather modest background in statistics, I'm sure it could be possible to make them more accessible. Take Laszlo Babai's paper on graph isomorphism in quasipolynomial time [2]: all you have to know in advance to understand it is some basic vocabulary of graph theory and algebra, and you can readily find them even on Wikipedia. He lays out definitions clearly and even goes as far as as presenting Latin equivalents of Fraktur letters (I wouldn't bother). Taleb seems more interested in establishing profundity by obscurity (what Charles Seife calls "proofiness"), like some kind of post-modernist philosopher. Come to think of it, Taleb seems very much like one. (I know I'm being trolled, but...) [1] http://www.fooledbyrandomness.com/PPAlgo2.pdf [2] http://arxiv.org/abs/1512.03547v1
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Luca Beurer-Kellner, Beat Buesser, Ana-Maria Creţu +11
As AI agents powered by Large Language Models (LLMs) become increasingly versatile and capable of addressing a broad spectrum of tasks, ensuring their security has become a critical challenge.
Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi +2
The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages.