G. Phi. Fo. Fum.
Update (Dec. 14): The long wait is over! Here’s Laci’s paper on the arXiv. So far, I’ve read it only deeply enough to note that it contains the following sentence:
A group G ≤ S(Ω) defines the category of G-isomorphisms of strings on the domain Ω; the natural notation for this category, the central object of study in this paper, would seem to be “G-Strings.”
With that, I believe Laci himself has outshone even reddit’s attempt to mine his breakthrough result for juvenile humor.
See also a nice Quanta article about Laci’s algorithm by Erica Klarreich. There’s only one statement in the article that I disagree with: namely that, if graph isomorphism were inherently quasipolynomial time, then it would be the first natural example of such a problem. We know other natural problems, like approximating free games and socially-optimal Nash equilibria, that are solvable in nO(log n) time but that can’t be in P unless 3SAT is solvable in ~exp(√n) time.
Update (Nov. 17): Video of Laci’s first talk is now available.
Breaking News (Nov. 12): Jeremy Kun has written up a phenomenal summary of Babai’s first lecture. I haven’t carefully studied all of it, and in any case, there are many missing details to be filled in later (Babai told Kun that the preprint will be available “soon, soon!”). But from the summary, four points stood out to me:
- Babai actually claims a quasipolynomial-time algorithm for an interestingly more general problem than graph isomorphism, called string isomorphism. This was already in the abstract, but googling didn’t reveal what string isomorphism was. So, OK, here’s what it is: you’re given two strings x and y over some finite alphabet, as well as the generators of a group G of permutations of the string indices. The problem is to determine whether you can transform x to y by applying a permutation in G. Or even more generally: given a string x, find a full set of generators for the subgroup of G that fixes x. See Kun’s post for the straightforward reductions from GI to these group-theoretic problems.
- As was hinted in the abstract, in Babai’s analysis of his algorithm, there’s one step that relies on a statement whose only known proof depends on the Classification of Finite Simple Groups. (Thus, it’s not the algorithm itself requires iterating through all the sporadic simple groups or anything like that; this only shows up in the correctness proof.) This is not the first-ever computer-science application of the Classification of Finite Simple Groups (indeed, Babai himself has some previous ones), but it’s certainly the most dramatic.
- In previous work on GI, the Johnson graph emerged over and over as a forehead-bangingly hard case that caused numerous algorithms to fail. In the new work, it looks like Babai’s central technical innovation is to show that, in some sense, the Johnson graph is the only obstruction to taking the divide-and-conquer approaches that people that had tried before, and making them run in quasipolynomial time. I.e., in each step of the recursion, either you can find a Johnson graph on a large fraction of the vertices and handle it specially, or else you can do something that works whenever there’s not a Johnson graph on a large fraction of the vertices. Babai calls this “split-or-Johnson.”
- Babai stressed that in some sense, his new algorithm is the culmination of a program laid out by Eugene Luks in 1982. Now, the Classification of Finite Simple Groups was also more-or-less completed in the early 1980s. To my mind, this raises a fascinating socio-mathematical question: which aspects of the new work, if any, could not have been done in the early 80s, possibly by Babai or Luks themselves? what is it that needed another 30 years? If the answer turns out to be “nothing,” then to me that’s an astounding illustration of the role of the individual in mathematical progress. As in: Laci was nice enough to take a third-of-a-century break between his and Luks’ work in the early 80s, and the “natural next step” in their program … and still no one managed to use that break to beat him to the next step!
Earlier today, I was tipped off to what might be the theoretical computer science result of the decade. My source asked me not to break the news on this blog—but since other theory bloggers (and twitterers) are now covering the story, I guess the graph is out of the Babai.
According to the University of Chicago’s theory seminar calendar, on Tuesday of next week (November 10), the legendary Laszlo Babai will be giving a talk about a new algorithm that solves the graph isomorphism problem in quasipolynomial time. The previous fastest algorithm to decide whether two n-vertex graphs G and H are isomorphic—by Babai and Luks, back in 1983—ran in exp(√(n log n)) time. If we credit the announcement, Babai has now gotten that down to exp(polylog(n)), putting one of the central problems of computer science “just barely above P.” (For years, I’ve answered questions on this blog about the status of graph isomorphism—would I bet that it’s in BQP? in coNP? etc.—by saying that, as far as I and many others are concerned, it might as well just be in P. Of course I’m happy to reaffirm that conjecture tonight.)
Next week, I assume, Laci will lecture to a packed house; then the experts will race to unpack the details. Until then, we probably need to sit tight; I don’t know any more than what’s in the abstract. For now, I’m delighted if commenters want to share general thoughts or questions about graph isomorphism (and I’ll try to answer what I can), but I won’t allow uninformed speculations or rumors about the details of the new result—not until Laci has had a chance to speak.
Update (Nov. 5): While we all wait with bated breath for more details, you can amuse yourself with the talk I gave at Laci’s 60th birthday conference five years ago.
Also, a comment of mine that I should probably promote to the main post:
Dana points out to me that non-native English speakers might not get the staggeringly clever pun in this post’s title (hey, it was the best I could do on a deadline).
So, alright, fee fi fo fum is what the approaching giant bellows in Jack and the Beanstalk. It means something big is on the horizon. Also, G is a graph, and Phi is an isomorphism.
Update (Nov. 12): So, Laci gave his talk. Video was made but does not appear to be available yet. However, Gabriel Gaster, who was in attendance, graciously live-tweeted everything. Here’s a Storify of the live-tweets. (What’s a “Storify”?)
Follow
Comment #1 November 4th, 2015 at 1:28 am
Amazing!
Comment #2 November 4th, 2015 at 2:07 am
As one of my favorite open questions in complexity theory (and one that I would have _loved_ to conquer myself…) this sounds like an incredible result. GI is one of the only problems in Karp’s original papers on NP-completeness whose complexity is still in question (besides all of that P vs NP stuff…)
Assuming this result holds, it would be a gem of TCS, and an incredible thing to witness in real time.
I’m also not surprised. I’ve felt like this problem is very “ripe” for such a result, and a lot of evidence suggested that GI would end up in some “easy” class.
Comment #3 November 4th, 2015 at 4:11 am
I wonder how different this new algorithm is from their previous one, and whether the methods can be generalized to the quantum setting. Will the talk be available online?
Comment #4 November 4th, 2015 at 4:15 am
I have a couple of questions, Scott:
Are there other NP-Intermediate candidates with quasipolynomial algorithms, or would this be the first?
Am I correct in assuming that even if GI was in fact contained in P, the “only” complexity theoretic implication would be to strike it (and problems that reduce to it) from the list of NPI candidates? i.e. it wouldn’t imply anything new about complexity classes. Still a huge result by Babai, of course, just wanted to make sure that I understand the context properly.
Thanks!
Comment #5 November 4th, 2015 at 6:40 am
Question from a complete outsider: can you explain the difference between quasi- and non-quasi polynomial? How close are they in practical terms?
Comment #6 November 4th, 2015 at 6:47 am
[…] Lazlo Babai, U.Chicago Seminar, 10 Nov., Graph Isomorphism in Quasipolynomial Time, here. See Aaronson as well, here. […]
Comment #7 November 4th, 2015 at 6:50 am
The current best result for group isomorphism is I think
n^(1/2 \log n + o(log n))
due to Rosenbaum https://rjlipton.wordpress.com/2013/05/11/advances-on-group-isomorphism/
Note that n^(1/2 log n) = e^( (1/2) (log n)^2). Group isomorphism is reducible to graph isomorphism with some blowup, so it seems that unless this new algorithm has a very low degree polynomial for the polylog part it might not say much new about group isomorphism unless the graphs from gets from groups look somehow special. This prompts two questions:
A) How bad is the blowup in reducing group isomorphsim to graph isomorphism?
B) Is there any nice graph theory properties one can say about the graphs one gets when one reduces group isomorphism to graph isomorphism?
Comment #8 November 4th, 2015 at 7:01 am
I actually do have one question. Is it reasonable to believe there is some path to showing GI is in coQMA in a way similar to group nonmembership? From my understanding, the only analogous step missing is that while Arthur can verify (via a swap test) that a given state is a superposition of an isomorphism class, he has no way of telling if that isomorphism class has anything to do with the graphs in question!
it seems so close to working, and yet, so far…
Comment #9 November 4th, 2015 at 8:07 am
Vitor #4:
Are there other NP-Intermediate candidates with quasipolynomial algorithms, or would this be the first?
No, there are others—and for some, we even have good evidence that quasipolynomial time is the best possible (e.g., if it’s not then 3SAT is solvable in subexponential time, or certain parameterized classes collapse). Three examples are calculating the VC dimension of a set, finding an approximate Nash equilibrium of a two-player game, and approximating the value of a free game.
Am I correct in assuming that even if GI was in fact contained in P, the “only” complexity theoretic implication would be to strike it (and problems that reduce to it) from the list of NPI candidates? i.e. it wouldn’t imply anything new about complexity classes.
Yes, that’s completely right, and it’s one of the basic reasons why many of us conjectured GI might be in P (another big reason being the extreme difficulty of finding hard instances in practice).
In fact, the main implication for complexity theory, is that we’d have to stop using GI as our flagship example of a problem that has statistical zero-knowledge proof protocols and dozens of other amazing properties, despite not being known to be in P, which would make all those properties trivial. 🙂 It’s similar to how the main implication of PRIMES in P, was that we had to stop using primality as our flagship example of a problem that was known to be in randomized polynomial time but not deterministic polynomial time. Still, I managed to adapt in my undergrad class, by talking about the randomized test for primality, and then treating the fact that it’s actually in P as just a further amazing wrinkle in the story. And I’d be happy to adapt similarly in the case of GI…
Comment #10 November 4th, 2015 at 8:18 am
luca #5:
can you explain the difference between quasi- and non-quasi polynomial? How close are they in practical terms?
Just so everyone’s on the same page: quasipolynomial means upper-bounded by 2(log n)^k for some constant k, whereas polynomial means upper-bounded by nk = 2k(log n) for some k.
In practice, I think, a quasipolynomial-time algorithm is better than an n50 algorithm, but worse than an n2 algorithm. Unless the constants are absurd, it’s certainly a lot better in practice than an exponential algorithm.
But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it.
This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P.
Comment #11 November 4th, 2015 at 8:27 am
Joe #8:
Is it reasonable to believe there is some path to showing GI is in coQMA in a way similar to group nonmembership?
All I can tell you is that various extremely smart people (not me) have worked on exactly that question over the past 15 years, and there’s always been some little problem that kills it in the end. (Much like with the still more ambitious dream of putting GI in BQP, by solving the hidden subgroup problem over the symmetric group.)
FWIW, my uninformed outsider’s view was always that even if GI is ultimately easy, these abstract, purely group-theoretic approaches probably just don’t know enough about graphs to prove it—and even if the abstract approaches are quantum-enhanced (or coQMA-enhanced), that still never seemed like enough to make up the difference. So I always put much more stock in approaches that knew more about graphs—that were specialized to that isomorphism problem, rather than any possible isomorphism problem that anyone could make up.
Comment #12 November 4th, 2015 at 8:37 am
Incidentally, Dana points out to me that non-native English speakers might not get the staggeringly clever pun in this post’s title (hey, it was the best I could do on a deadline).
So, alright, fee fi fo fum is what the approaching giant bellows in Jack and the Beanstalk. It means something big is on the horizon. Also, G is a graph, and Phi is an isomorphism.
Comment #13 November 4th, 2015 at 9:25 am
It might be worth mentioning in the main body of the post that prior to Babai’s discovery there was no known quasi-polynomial-time quantum algorithm for GI. (Or please correct me if I’m mistaken about that.)
Comment #14 November 4th, 2015 at 9:33 am
OK, embarrassingly simple question, but I suspect other non-experts are wondering:
So the new algorithm is in exp(polylog(n)) which is in quasipolynomial time and between polynomial time and exponential time.
So far so good.
And the old (previously best known) algorithm is in exp(√(n log n)) which(presumably and hence the excitement) is not in quasipolynomial time.
Question: Is the old algorithm in exponential time, or is it also in that intermediate zone between polynomial time and exponential time?
Also, thanks for explaining the title pun – good one!
Comment #15 November 4th, 2015 at 9:42 am
Gus #13: Yes, that’s completely right, but I don’t think I ever suggested in the post that a quasipolynomial-time quantum algorithm for GI was known (and if it were known, clearly I would’ve said something about it, so one could infer from my silence that it wasn’t… 🙂 ).
Comment #16 November 4th, 2015 at 9:54 am
Robert #14: Whether to call things like exp(√n) “exponential,” “subexponential,” or something else is a terminological question people have quibbled about for years—we even had a whole thread about it long ago on this blog. Ultimately, though, it doesn’t matter. The important point is that, if you just look at the functions, npolylog(n) is clearly “within the polynomial-time greater metropolitan area,” just somewhat on the high side, whereas exp(√n) is clearly “within the exponential-time greater metropolitan area,” just somewhat on the low side. So I’d say that the difference between the two is conceptually huge.
(Addendum: It’s actually possible to prove that any function obtained by iteratively adding, multiplying, powering, and taking exponentials and logs will be either “in the polynomial greater metro or below,” or else “in the exponential greater metro area or above”—i.e., that there really is a sharp jump between the two, with no functions in this class in the middle. The functions that do fall between the two, e.g. the “half-exponential” functions (functions f such that f(f(n)) is exponential), have no closed-form expressions. So, in that sense, the polynomial and exponential “greater metro areas” really do have a well-defined existence. For more about this, see this MathOverflow question and answer.)
Comment #17 November 4th, 2015 at 9:57 am
Does this mean cryptography is doomed and we should Start Panic?
Comment #18 November 4th, 2015 at 10:04 am
freckl #17: Not at all. No one has ever based a practical cryptosystem on graph isomorphism, in part because we’ve known for decades that the problem is easy in practice. (See also my comment #10.)
Comment #19 November 4th, 2015 at 10:35 am
Scott #18: For many examples GI is very simple and the “just run NAUTY” approach works well. This is probably due to the fact that GI (and Graph Automorphism) are simple for graphs with low eigenvalue multiplicity. The region where NAUTY (and all previous GI algorithms) fail is when the graphs are highly structured (as in, the Automorphism group is non trivial (in a human sense)). For those graphs, NAUTY fails miserably (or so I’ve heard).
My feeling is that if this result is true, it will have some profound implications. Do you have any idea of what the fundamental idea is? And is there a preprint somewhere?
freckl #17: There might be other cause for worry:
https://www.youtube.com/watch?v=33RbRid1deo
https://eprint.iacr.org/2013/400.pdf
(note: I haven’t read the paper)
Comment #20 November 4th, 2015 at 11:41 am
Scott,
Why did your source not want you to “break the news”? It’s not like you are passing on a rumor or extrapolating from a cryptic abstract. Babai made an announcement by publishing that talk title. Why keep that secret?
Abe,
Random numbers are hard to factor, while random graphs are easy to distinguish (under obvious distributions). Miyazaki produced graphs on which Nauty takes exponential time, but I think it’s a lot harder than symmetry and eigenvalue multiplicity. Tener showed how to solve Miyazaki instances quickly and I think that is the state of the art: that no one knows how to produce instances that are hard for all known algorithms, not even quasi-polynomial hard. But I’ve always been confused by this literature.
Abe₂,
That paper is (I assume) correct and the previous L(1/4) algorithm by Joux was implemented and demonstrated to break actually deployed cryptography. But such cryptography is rare because people were always suspicious of small characteristic fields. The practical question is whether such techniques will be extended to prime field DH, factoring, or ECC. None of these possibilities seem likely, but if you had to work on attacking the underlying mathematics of these systems, this is the most promising lead. (Among those three, small characteristic ECC seems most likely to me. That is less popular than prime ECC, but a lot more popular than small characteristic DH.)
Comment #21 November 4th, 2015 at 11:55 am
I think the biggest surprise to me if we get GI in P would be that GNI would then also be in P and thus coNP
Whenever I’ve taught or explained Interactive Proofs I’ve started with showing an interactive proof for Graph Non-Isomorphism which was always meant to be surprising…because, how could you prove two graphs are non-isomorphic without going through all the possible isomorphisms?! And then interaction always comes to save the day.
You said that you’ve always sort of assumed it was in P…did GNI being easy or having short proofs not bother you?
Is there some intuition you have on why GNI is no biggie either?
Or, I guess, an easy problem is an easy problem, huh?
Comment #22 November 4th, 2015 at 12:29 pm
Manuel #21: Well, I always assumed GNI was in coNP (much more confidently than I conjectured it was in P), since we knew from Klivans and van Melkebeek that that follows from good enough pseudorandom generators existing. The only reason for the interactive protocol is then that we can’t prove unconditionally that the PRGs work (and possibly also the statistical zero-knowledge aspect).
Comment #23 November 4th, 2015 at 12:43 pm
Douglas Knight #20: As far as I know, GI for graphs with low eigenvalue multiplicity have polynomial time algorithms to solve them. All graphs that have low eigenvalue multiplicity being easy doesn’t imply all graphs with high eigenvalue multiplicity are hard. It’s a necessary but not sufficient condition. My point is that choosing a ‘random’ graph (in the Erdos-Renyi sense I guess) will most likely produce graphs with low eigenvalue multiplicity and thus produce easy cases for NAUTY.
Factoring integers is actually very easy most of the time. All you have to do is check a bunch of small prime factors. To find cases where factoring is hard you have to find large primes, that themselves don’t have small prime factors for their multiplicative group (and I think a host of other properties). Primes occur with regular enough frequency that you can generate hard instances but picking random large numbers are most of the time very easy to factor.
I am no expert but from my noodling around on the Internet I thought it was ‘easy’ to produce hard GI instances by piggy backing off of group isomorphism (doing something like producing Cayley graphs of the small-ish groups and permuting vertices) but I of course could be wrong.
Thanks for the information on ECC, DH and the like. I’m only knowledgeable enough to catch the highlights and haven’t gotten to digging in further.
Comment #24 November 4th, 2015 at 12:48 pm
How often is a result announced like this? I cannot think of another example in computer science.
Comment #25 November 4th, 2015 at 1:03 pm
Douglas #20, Noah #24: My source understood full well that the abstract was publicly available, but had a feeling that nevertheless, Laci wouldn’t want an online blog-circus wildly speculating about his result with no details. So I said, sure, I certainly sympathize with that, so I promise I won’t be the one to break the story. But in the age of social media, I can guarantee that even if you and I do nothing, news of this abstract will spread exponentially across the nerd world anyway. (But I thought it might take a few days, rather than just a few hours, which is what happened.)
No, I can’t remember any other major math or TCS result that was announced this way (though it’s entirely possible that I’m forgetting something, or that such a thing happened before my time). I have the impression that these sorts of teasers are more common in fields like astronomy and experimental physics.
Comment #26 November 4th, 2015 at 1:12 pm
Abe #23: Your claims are interesting and plausible, but the folklore I had heard was a little different.
Firstly, yes, GI is known to be in P assuming bounded multiplicity of eigenvalues. But I had thought that even when you have huge eigenvalue multiplicity, finding hard GI instances that remain hard for a long time was itself a hard problem. I.e., I had thought there was an iterative process, where first people would propose a hard instance, then others would propose a new algorithm that handles the instance, then others would propose a new instance that breaks the algorithm, and so forth, rather than there being any single family of instances that could withstand all the algorithms in practice.
I had also thought that factoring a random integer is plausibly conjectured to be (sub)exponentially hard classically, just with a milder (sub)exponential than factoring the product of two huge primes. For while you can easily pick off the small factors, a random integer will also have a few large-ish prime factors w.h.p.
But maybe someone who’s actually an expert on these problems could enlighten both of us?
Comment #27 November 4th, 2015 at 1:16 pm
Scott #20 The first hint of Wiles’ solution of Fermat was the announcement of a lecture at a conference in Cambridge,
and everyone knew (guessed, really) what he would announce. But iirc his title was somewhat cryptic.
Comment #28 November 4th, 2015 at 1:40 pm
Nick #27: I had thought that only during the course of Wiles’ famous 1993 lectures, did it become clear where he had to be going! But I’m sure some in the audience caught on faster than others. 🙂
Comment #29 November 4th, 2015 at 1:49 pm
Scott, Noah’s #24 question makes me wonder how you might go about announcing a similarly ground-breaking result after passing peer review since there is probably no single correct answer.
Comment #30 November 4th, 2015 at 1:49 pm
Abe,
No, factoring random integers is hard. Random integers have many small factors, so it is easy to find one factor, but they also have many large factors, so it is hard to find all the factors.
What is the probability that a number n has all factors less than n^1/k? Ignoring multiplicity, the size of the product of all the factors less than n^1/k is the product of the primes that do divide. Take logarithms and it is the sum. It is the sum of the contribution, log(m), times the indicator of whether it contributes. Its expected value is that log(m) times the probability that m divides, 1/m, times the probability that m is prime, 1/log(m). Thus we have the harmonic integral and the expected logarithm of the product of the small factors is log(n)/k. Thus the probability that it only has short factors is at most 1/k. So, the probability that a b bit number has no factors with more than b/100 bits is less than 1%. So that’s a running time of something like exp((b/100)^1/3), which still L(1/3). Even if you were promised that your number had b^1/2 factors each with b^1/2 bits, that would only improve the algorithm from L(1/3) to L(1/6).
Comment #31 November 4th, 2015 at 1:54 pm
Nick, I think that very few people guessed what he would announce, but those people shared their guess, so the talk was well-attended.
Comment #32 November 4th, 2015 at 2:02 pm
Based on the abstract, it sounds like Laci may not have crossed the ts and dotted the is yet, which might explain why he is giving a talk instead of a wider announcement.
Comment #33 November 4th, 2015 at 2:03 pm
Scott,
As far as I can tell, that iteration has happened only once. Miyazaki exhibited graphs on which nauty took exponential time and 10 years later Tener produced an algorithm that quickly exhibits isomorphisms for Miyazaki’s graphs.
Note that there is an asymmetry. If you have a pair of non-isomorphic graphs, you have an invariant that distinguishes them that you can add to any algorithm (if it is polynomial time). But Miyazaki had a graph on which nauty’s canonical labeling took a long time, so it was not clear where to even begin.
Comment #34 November 4th, 2015 at 2:07 pm
Douglas #33: OK, thanks for clarifying!
Comment #35 November 4th, 2015 at 2:14 pm
Michael #29:
[I] wonder how you might go about announcing a similarly ground-breaking result…
May we all face such problems. 😀
I’m one of the worst people on earth at keeping secrets, so I’m sure I’d end up blurting out a premature announcement (probably by blog comment…) were I ever in this situation, but I’ve never been in this situation. So I’m not the one to ask.
Comment #36 November 4th, 2015 at 4:40 pm
Scott #16: Wow wow wow! So you are saying that there is a well-defined family of “polynomial-like” functions (namely those with exponentiality 0), and a well-defined family of “exponential-like” functions (with exponentiality 1), such that no algorithm known in computer science has a complexity that falls “in between” those families?
Well, doesn’t this call for redefining P as the first family, and EXP as the second family? Those seem to capture better our intuition about easy and hard problems, as nobody seems to care much whether Graph Isomorphism is actually in P, or it has been “merely” proven to be solvable in quasipolynomial time.
Comment #37 November 4th, 2015 at 4:45 pm
It may be worth noting that there is a fast randomized algorithm that generates a uniformly random integer in a given range along with its prime factorization (of course generating random products of two primes along with its factorization is also possible…)
Comment #38 November 4th, 2015 at 5:04 pm
Scott #22:
Ah, I guess I thought about the IP protocol for GNI as an AM protocol before and I knew that we can derandomize with much-believed circuit lower bounds and thus get MA=AM=NP, but I guess I never put the two together to see that this would (conditionally) put GNI in NP…
Thanks, that’s a good paper to have too!
Comment #39 November 4th, 2015 at 5:20 pm
Is there any kind of streaming for the event?
Comment #40 November 4th, 2015 at 5:38 pm
Mateus #36:
So you are saying that there is a well-defined family of “polynomial-like” functions (namely those with exponentiality 0), and a well-defined family of “exponential-like” functions (with exponentiality 1), such that no algorithm known in computer science has a complexity that falls “in between” those families?
I didn’t quite say that. Half-exponential and even third-exponential functions do occasionally arise in complexity theory: for example, in circuit lower bounds and natural proofs. And even though these functions have no closed form, one can certainly design an algorithm that runs for a half-exponential amount of time (in other words, there are half-exponential functions that are time-constructible). On the other hand, it’s true that I don’t know of any natural example of an algorithm with a half-exponential runtime. (Does anyone else?)
Well, doesn’t this call for redefining P as the first family, and EXP as the second family?
I completely agree—we could take “exponentiality of 0” as our expanded criterion for efficient (generalizing poly(n)), and take “exponentiality of 1 or greater” as our expanded criterion for very inefficient (generalizing exp(poly(n))). I suppose the only reason this hasn’t been done is that, in practice, it tends to be only a few kinds of functions from the “suburbs” of polynomial and exponential that ever show up, such as npolylog(n) and exp(nε), so people have been content to deal with them on a case-by-case basis.
But if the functions ever got really wild, then I think this proposal is exactly right!
Comment #41 November 4th, 2015 at 6:17 pm
Since you guys are discussing NAUTY, I thought I’d mention
SAUCY. It is typically way faster and handles Miyazaki graphs just fine.
Comment #42 November 4th, 2015 at 7:13 pm
Over five years ago there was a 60th birthday conference for Babai, which got me wondering about other cases where someone his age has made a major algorithmic advance. Mathematical breakthroughs by the Medicare eligible must be rare enough, but graph algorithms in particular always seemed like more of a young man’s game where IMO/Putnam style cleverness outweighs experience.
Comment #43 November 4th, 2015 at 10:19 pm
A GI related problem i’ve wondered about is that of identifying the lowest isomorphic form of a graph.
That seems roughly like the type of optimization problem that’s NP-Hard and a candidate for an adiabatic QC. But, is it even in NP?
BTW, would an eventual result showing that GI is in P affect your confidence that Integer Factorization is not in P?
Comment #44 November 4th, 2015 at 10:42 pm
Job #43:
A GI related problem i’ve wondered about is that of identifying the lowest isomorphic form of a graph.
Do you mean, the first isomorphism of G in some lexicographic ordering? Interesting—I don’t see off the top of my head why that should be in NP, though it’s clearly in the second level of PH. The difficulty might also depend on exactly how we define ‘lexicographic ordering’ (i.e., on how the graphs are encoded as strings).
Your problem is related to, but potentially much harder than, the well-known problem of graph canonization (which just asks for some canonical form for a graph, not necessarily the first one in some fixed lexicographic order).
BTW, would an eventual result showing that GI is in P affect your confidence that Integer Factorization is not in P?
Not much; the two questions seem extremely different to me. For GI, as I said, we’ve had good reasons for decades to suspect it’s in P, or at any rate in quasipolynomial time or something. And we never had particularly good ways to generate hard random instances. For factoring, by contrast, it’s easy to generate random instances that appear to engage the full difficulty of the problem. And I’d say the situation is that factoring might be in P—it’s much more plausible than for the NP-complete problems—but we’ve never had a positive empirical case for expecting it to be in P, as we’ve arguably had for GI. Factoring in P would be an incomparably bigger surprise.
Comment #45 November 4th, 2015 at 10:54 pm
Right, using some standard representation. I think this would be incredibly useful in practice but i don’t see it being easy even in the average case.
BTW, i remember reading at some point that GI would be efficiently solvable if we could access quantum amplitudes.
If GI were shown to be in P then would we gain no advantage from being able to access quantum amplitudes?
Comment #46 November 4th, 2015 at 11:05 pm
Job #45:
BTW, i remember reading at some point that GI would be efficiently solvable if we could access quantum amplitudes.
People have been working on that for 20 years, but no one has succeeded in finding a polynomial-time quantum algorithm for GI.
If GI were shown to be in P then would we gain no advantage from being able to access quantum amplitudes?
Obviously, if GI were in P, then you could at most hope for a polynomial speedup from a quantum computer.
Comment #47 November 4th, 2015 at 11:16 pm
[…] exciting and I immediately posted the result on Facebook last night only to see it on other main TCS blogs and on twitter the next […]
Comment #48 November 4th, 2015 at 11:39 pm
Noah #24: Santos’ counterexample to the Hirsch conjecture was also “announced” by a talk title and abstract.
https://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/
Comment #49 November 5th, 2015 at 12:28 am
Actually, i was thinking of your “Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories”, i was just confused.
From the abstract:
GI being one of those problems. From this perspective, it sounds like a result placing GI in P would make sampling the history of a hidden variable less problematic.
Comment #50 November 5th, 2015 at 5:11 am
Sorry, what’s the definition of exponentiality?
Comment #51 November 5th, 2015 at 7:19 am
Job #49:
From this perspective, it sounds like a result placing GI in P would make sampling the history of a hidden variable less problematic.
Well, not really. What I showed in that paper, was that sampling the history of a hidden variable would let you efficiently solve all problems in SZK (Statistical Zero Knowledge). Now, GI is the most famous problem in SZK that’s not known to be in BQP, so I used that as my big example. But there are plenty of other SZK problems that wouldn’t be touched by GI being in P, and that could still make sampling hidden variables “problematic” (meaning: hard to simulate with an ordinary quantum computer). There are even other examples that are also isomorphism problems, like ring isomorphism and multivariate polynomial isomorphism.
Comment #52 November 5th, 2015 at 7:53 am
Sniffnoy #50: That’s a fantastic question. I don’t know the correct definition of exponentiality, though presumably it’s somewhere in the references on transseries cited in this MathOverflow thread. All I can tell you is how, on reflection, I would define it.
Let f be positive and increasing on all sufficiently large reals, and let χ(f) be the exponentiality of f. Then we recursively stipulate:
χ(x)=0 (thanks to the commenters for fixing an error here; I had previously said χ(1) should also be 0, when in fact it should be -∞)
χ(cf)=χ(fc)=χ(f) for all positive constants c
χ(f+g) = χ(fg) = max(χ(f), χ(g))
χ(exp(f)) = χ(f) + 1
χ(log(f)) = χ(f) – 1
Finally we stipulate that, if f is asymptotically bounded between two functions that both have exponentiality k, then f itself has exponentiality k.
All functions that aren’t in the closure of these operations, would not have an integer-valued exponentiality.
Exercise for the reader to extend this definition to fractional exponentialities: for example, to assign χ(f)=1/2 to f such that f(f(x))=exp(x).
Comment #53 November 5th, 2015 at 8:27 am
Scott #52: I think you also need to demand f to not be constant, otherwise you get an inconsistency, as χ(1) = 0, and χ(log(1)) = -1, and χ(exp(1)) = 1.
Comment #54 November 5th, 2015 at 8:52 am
Thanks Scott! Comment #16 was super helpful.
I think I had (and probably a lot of people out there still have) the impression that everything between poly(n) and exp(n) is just a vast continuous sea variously labeled superpolynomial or subexponential. Super cool to learn about the sharp dichotomy that we get if we only allow composition of elementary functions.
This makes me much more impressed with Babai’s claimed result.
Comment #55 November 5th, 2015 at 9:07 am
It is a bit stange for me how exponentiality is defined. I always thought that a function f is exponential (or supra-exponential) if there exists a c>1such that f(n) = Omega(c^n). A function f is polynomial (or subpolynomial) if there exists a k, such that f(n) = O(n^k). And those functions which are neither polynomial (subpolynomial) nor exponential (supra-exponential) are suprapolynomial and subexponential. What is the problem with this approach.
Comment #56 November 5th, 2015 at 9:10 am
Scott #40: I don’t recall ever seeing any mention of nondeterministic quasipolynomial time (or nondeterministic exponentiality-0 time), and a cursory search revealed only crickets (though maybe I’m looking for the wrong words). Are any natural problems suspected to lie in that class? What about ones being complete under quasipolynomial reductions?
Comment #57 November 5th, 2015 at 9:34 am
[…] don’t have much to add to Luca, Scott, and Lipton/Regan on the exciting announcement by Babai of a quasipolynomial time graph isomorphism […]
Comment #58 November 5th, 2015 at 10:28 am
Scott, I think you want χ(1)=-∞, not 0 (and χ(0) undefined).
Comment #59 November 5th, 2015 at 11:01 am
Mateus #53 and Douglas #58: OK, thanks very much for patching up my definition!
I should stress that I don’t know how well my definition matches that of the people who study “transseries”; anyone who knows is welcome to enlighten us.
Comment #60 November 5th, 2015 at 11:03 am
M.S. #56: Off the top of my head, I can’t think of any natural problem in nondeterministic quasipolynomial time that’s not known to be in NP. Anyone else have an example?
Comment #61 November 5th, 2015 at 11:12 am
Istvan #55: Yes, that handles the functions that are strictly polynomial or strictly exponential. The question we’ve been discussing in this thread, is how to formalize the phenomenon that there are slightly superpolynomial functions (including npolylog(n)), and slightly subexponential ones (including exp(√n)), and a sharp boundary between the two, which can be defined in practice by which side you fall on of the “fractional exponential functions” (those functions that are not exponential, but which yield exponential or superexponential functions if you compose them with themselves a constant number of times). The notion of the “exponentiality level” of a function is an attempt to capture this.
Unfortunately, the terminology is overloaded, with terms like “exponential,” “subexponential,” and “superexponential” used to mean different things in slightly different contexts. So, best just to define exactly what you mean by them whenever it’s important.
Comment #62 November 5th, 2015 at 12:00 pm
On the theory/practice side: chip designers use graph isomorphism algorithms to make sure the IC masks match the intended circuit. These run in linear time on graphs with billions of elements, since for human designed circuits, the first labelling steps typically result in lots of unique labels. Commercial programs also try to produce a small set of differences in the case of non-isomorphism. The smallest such set is an NP-complete problem, but fortunately an optimum such set is not needed, and in practice an OK but not optimum set can be obtained in linear time.
Engineers also compare the circuit as designed to the circuit as implemented, which may use differ gates in different combinations, as long as the function is equivalent. This is an NP complete problem, but in practice also runs in linear time, since human designers typically build bigger chips out of more of the same-size sub-networks, each of which can be compared independently. I suspect (without proof) this is due to computational limits of the human brain, and is the same reason big programs are made of more subroutines, not bigger subroutines.
Finally, engineers try to prove that the resulting networks have certain properties (non-deadlock, etc.) This is NP-complete or worse (some queries can be equivalent to the halting problem). The software tries to prove the result or find a counter-example, in general using heuristics since exhaustive search is prohibitive for realistic size problems. The run times vary wildly. Simple queries on small circuits may take forever while complex queries on large circuits may finish quickly. Results vary as well – sometimes it finds a proof or counterexample in a few seconds, sometimes it says it cannot prove it either way, and sometimes it runs until the user runs out of patience.
Comment #63 November 5th, 2015 at 4:09 pm
I recall from calculus class that when doing Laplace transforms there are functions called the alpha function and beta function which are defined by their Laplace transforms and have some very strange properties including that they’re very deeply in between polynomial and exponential. Unfortunately web searching isn’t turning up any info right now, but maybe one of those could serve as a dividing line between the two. There are some slightly more prosaic possible dividing lines, like f(f(n)) == e^n.
Comment #64 November 5th, 2015 at 6:28 pm
Just posted to the department calendar:
Babai will be giving a second talk on Thursday, Nov 12, titled “A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem”.
The full description is here:
http://www.math.uchicago.edu/calendar?calendar=Group+Theory
Comment #65 November 5th, 2015 at 6:58 pm
It somehow seems relevant that in 1990 László Babai wrote a paper about competition and communication between scientists in the internet age:
E-mail and the unexpected power of interaction
Here is how it concludes:
Comment #66 November 5th, 2015 at 9:27 pm
Worth noting from Zev’s link: Apparently, going by Zev’s link, the proof involves Schreier’s hypothesis, which I assume refers to the fact that the outer automorphism group of every finite simple group is solvable. But the only known proof of this fact goes by means of the classification of finite simple groups! (As in, here’s all of them, here’s their outer automorphism groups, look, they’re all solvable.) So implicitly that whole classification is being used here!
Comment #67 November 6th, 2015 at 5:03 am
Re #44, I have a question that probably isn’t too relevant for the TCS. For finite (simple) graphs, there’s at least an obvious exponential time algorithm that finds the permutation of the vertices that makes the graph the lexicographically smallest in some encoding.
But now suppose you care about infintie graphs. Let’s take a particular simple case: consider undirected graphs whose vertex set is omega, no multiple edges, and every vertex has a finite (but possibly unbounded) degree. Can you give a definition for an encoding (mapping the edge set to an infinite bit sequence) in which it’s guaranteed that there exists a permutation of the vertices of any such graph that gives the lexicographically smallest encoding? If I tried to define the encodings in some obvious way, it turned out that for some graphs there’s no smallest encoding.
Comment #68 November 6th, 2015 at 8:45 am
What I never understood is that although we don’t have an efficient algorithm to (always) find whether 2 given graph instances are isomorphic we do have known formulas to (efficiently) compute the exact number of unique (non-isomorphic) graph instances (for a given number of vertices and edges) – http://keithbriggs.info/cgt.html
Is this a “clue” that GI is indeed easy?
Comment #69 November 6th, 2015 at 9:02 am
I’m surprised that no one has mentioned the L-notation yet. A function f(x) is L[alpha,c] if f(x)=exp((c+o(1))(x^alpha)((ln x)^(1-alpha))) where 0 ≤ alpha ≤ 1. (Some definitions use x=ln n as the parameter, but this only makes sense for algorithms that take numbers as input.) The connection between alpha and the exponentiality for a function f is that if alpha>0 then the exponentiality=1, and conversely if the exponentiality<1 then alpha=0, at least if I understood the definitions correctly. In any case, the point is that the exponentiality isn’t the only way to measure where functions are between polynomial and exponential.
Comment #70 November 6th, 2015 at 10:59 am
Aula #69: I always found L-notation unintuitive to read, but in any case, from the current perspective it’s “just” a notation for picking out various functions in the exponential greater metropolitan area. It doesn’t have anything to say about the existence or nonexistence of a sharp dichotomy between “polynomial-like” and “exponential-like” for all “natural” functions, which is what the notion of exponentiality level tries to capture.
Comment #71 November 6th, 2015 at 11:47 am
I can’t.
On the other hand, i think you could show that, using a typical encoding that assigns one bit per edge (i.e. the upper or lower half of the adjacency matrix) the lexicographically smallest isomorphism for a graph would have its least significant k(k-1)/2 bits set to 1 where k is the size of the largest clique in the graph.
If that’s the case, an infinite graph would probably start with an unbounded number of 1s:
…11111111111
Comment #72 November 6th, 2015 at 5:43 pm
Scott, could you briefly explain why you call it the “result of the decade”? Is it because of the consequences (I am not aware of any major ones, other than the ones related to the problem itself)? Or because of it being such a popular problem that is “hot” and yet is hard to solve?
Comment #73 November 6th, 2015 at 7:04 pm
Abdallah #72: No, it’s not because of the consequences for anything else. It’s just because graph isomorphism is one of the most fundamental problems in theoretical computer science, and it’s not every day (or every decade) that something that basic gets moved from nearly exponential time to nearly polynomial time, in terms of the provable upper bound.
Comment #74 November 7th, 2015 at 2:14 am
Basic complexity theory question whose relevance will become apparent in a moment: Say we have a class of functions S. What are the conditions on S for DTIME(S) to be low for itself? What about DSPACE(S)? BPTIME(S)? BQTIME(S)?
Now the part that explains why these questions are relevant:
So I tried to look up this transseries stuff and came to the conclusion that I’m not going to understand this without a lot more effort. But, the noteworthy thing is that exponentiality of a composition is the sum of the exponentialities, as it should be. In particular, things of exponentiality 0 are closed under composition. Composition f o g of transseries isn’t defined in all cases, but I think it is whenever g goes to infinity, which are the only cases we care about here.
Anyway the closure under composition is the important thing I figure, because it means — or at least I think it means? — that if you considered the complexity class DTIME(all functions of exponentiality 0) it would be low for itself?
The reason I bring all this up is because of this earlier comment by you, where you suggest that this should be an important property of a complexity class to be considered “physically reasonable”. You list there P, BPP, and BQP; L and PSPACE; and NC. P, BPP, and BQP are all polynomial time on slightly different classes of computers (and not weird asymmetric ones like a nondeterministic Turing machine). L and PSPACE are space-based. NC I don’t know enough about and am going to ignore for now.
So like I said before, I realize I’m not actually entirely sure what the criterion is for a DTIME-defined (or BPTIME, or BQTIME) class to be low for itself — I would have thought it’s just being closed under composition, but I realize I don’t actually know. (And as for space, that’s even less clear to me.)
But my point is, if that is the condition, then all your “physically reasonable” classes defined in terms of polynomial time, you could replace that with exponentiality-0 time and still have a physically reasonable complexity class. Or with quasipolynomial time! Since the composition of e^((log n)^k) and e^((log n)^m) is e^((log k)^km). This seems to generate a bunch of physically reasonable complexity classes by your earlier criterion.
But I’m worried that I don’t have the complexity theory right and closure under composition isn’t actually what we need? Hence the initial question.
(Though I suppose descriptive complexity theory may give us a reason to prefer the more usual complexity classes…)
Comment #75 November 7th, 2015 at 9:55 am
Sniffnoy #74: I agree that the exponentiality-0 functions are closed under composition, and that that fact implies that DTIME(exponentiality 0) (like P and DTIME(npolylog n)) is self-low. Notoriously, the same isn’t true for exponential functions, so that EXPEXP is a much larger class than EXP.
Comment #76 November 7th, 2015 at 3:42 pm
OK, so that does give a way to generate lots of such classes; I assume the same holds for BPTIME and BQTIME? Notably QP is generalized by DTIME(f(poly(f^-1(n))) for various f (so long as you pick f such that the result includes P).
Space seems to require composition and addition. (I guess time technically requires composition and multiplication, but you don’t ususally care about time below polynomial…) So you not only get L and PSPACE but also QPSPACE and etc.
And then these should be combinable, so SC should work, right? (Or really if I’ve got this right you can get a slightly weaker condition on time which I’m not going to bother to write out here.) It seems these are easier to generate than your earlier comment suggested.
(Yes I realize this should be easy, I got confused about L vs EXPSPACE earlier for some reason and as a result got confused about the whole thing, I’m pretty sure I’ve unconfused myself now.)
Comment #77 November 8th, 2015 at 3:38 am
The atmosphere around Wiles’ FLT lectures is described here:
http://www.dms.umontreal.ca/~andrew/PDF/FLTatlast.pdf
For the Cambridge conference, Wiles had
announced his lectures, a series of
three given on successive days, with the
highly unspecific title “Modular Forms,
Elliptic Curves, and Galois
Representations.” Prior to his
lectures, he refused to give a hint as
to what they might contain. Even
though, by the third talk, many in the
audience had guessed he might have
cracked Fermat’s Last Theorem, few
dreamt that he could have proved so much
more, and there was an audible gasp as
he wrote the final result on the
blackboard.
(Wiles had actually proven something more general than FLT, from which FLT fell out as a consequence). That’s much different than if he had announced an FLT proof ahead of the conference. I guess there’s at other times been an interval between announcing a result, and having a paper or preprint ready to circulate. Still this seems a bit surprising.
Comment #78 November 8th, 2015 at 12:46 pm
An announcement of three talks (to be held on campus) by L. Babai in the next several weeks can now be found on the website of the University of Chicago’s Mathematics Department, where Babai also holds a faculty position.
https://math.uchicago.edu/
The abstracts for the talks are available. The first one is found here https://calendar.google.com/calendar/event?eid=czNzOXNtZ2tydG00OG5obDJlZ3I3c21uY2cgYzU3c2hpY2k0NW0xN3FsMGdodmw1NmVrMzhAZw&ctz=America/Chicago
Comment #79 November 9th, 2015 at 7:46 pm
[…] Trevisan already has made a post on this result, and Scott Aaronson likewise. Luca further promises to be in Chicago next Tuesday when László gives his talk on […]
Comment #80 November 10th, 2015 at 10:48 pm
Any updates from the frontline? The talk is delivered by now?
Comment #81 November 11th, 2015 at 1:51 am
Rahul #80: Yes, Gabriel Gaster live-tweeted the talk. More discussion on Luca’s and Lance’s and Dick Lipton’s blogs. It doesn’t seem like video is available yet (but photos of the lecture hall show a video camera there).
Comment #82 November 11th, 2015 at 4:20 am
Scott #81:
Fascinating! When can we expect a Scott update on this? 🙂
Sounds like a Stop Press moment for TCS. Special blog-post, midnight edition? 🙂
Comment #83 November 11th, 2015 at 7:43 am
Rahul #82: Alas, I wasn’t there, and I prefer not to write about it based on secondhand Twitterstorms—maybe I’ll write something once a paper (or video of the talk) becomes available.
Comment #84 November 11th, 2015 at 8:34 am
I’m hoping this will lead to a practical efficient GI algorithm (will depend on that “polylog” constant I guess).
Comment #85 November 11th, 2015 at 10:23 am
fred #84: As discussed earlier in the thread, we already have GI algorithms that are efficient in practice (almost certainly more so than this one, for almost any graph anyone can devise).
Comment #86 November 11th, 2015 at 4:02 pm
Scott, would it be possible for you to do an informal 30-60 min blackboard video lecture explaining the context and confines of this problem and its implications? Pretty please.
Thanks.
Comment #87 November 11th, 2015 at 4:06 pm
Will (has) Laszlo Babai’s, talk on this algorithm be posted as online video? Where? When? Note: I’ve tried to wade through several of his online lectures… not exactly easy to follow. Which is why I’ve asked if you might give it a whirl. Thanks again.
Comment #88 November 11th, 2015 at 4:08 pm
Randall #86: Sorry, don’t have time, and there are people much more expert than I to do it. The graph isomorphism Wikipedia page should give you a decent start.
Comment #89 November 11th, 2015 at 5:43 pm
Randall #87: I already said above, I don’t know when the video will be available.
Comment #90 November 11th, 2015 at 6:09 pm
Scott – “almost certainly more so than this one, for almost any graph anyone can devise”
Well no, not quite. If you have any sprawling algorithm that is still negotiable, then you are free to co-opt any other more practical algorithm by running it in parallel. In that sense, we don’t really do algorithms in complexity theory, we only do complexity bounds. (Which may look like algorithms if they are upper bounds.)
Comment #91 November 11th, 2015 at 6:13 pm
Greg #90: You know what I meant.
Comment #92 November 12th, 2015 at 12:44 am
Naive question: Can this result be taken as a infinitesimal baby step towards P=NP?
i.e. If eventually all outstanding NP-intermediate problems (like GI was till now) are shown to be in P then P=NP, correct?
Another question: To show that NPI is empty (& hence P=NP), is it sufficient to provide quasi-P algorithms? Or must we still search for strictly-P algorithms for problems that have a quasi-P algorithm?
Comment #93 November 12th, 2015 at 1:14 am
Rahul #92:
Can this result be taken as a infinitesimal baby step towards P=NP?
Only with such massive emphasis on the “infinitesimal,” that the answer is effectively no.
If eventually all outstanding NP-intermediate problems (like GI was till now) are shown to be in P then P=NP, correct?
Yes, by Ladner’s Theorem. But keep in mind that there are infinitely many such problems—and that proving P=NP by solving an NP-complete problem would merely require solving one of them!
To show that NPI is empty (& hence P=NP), is it sufficient to provide quasi-P algorithms? Or must we still search for strictly-P algorithms for problems that have a quasi-P algorithm?
It shouldn’t be hard to show that, if there’s a quasipolynomial algorithm for every NP-intermediate problem, then NP is contained in quasipolynomial time. So, that’s not quite P=NP, but morally it’s almost the same.
Comment #94 November 12th, 2015 at 1:39 am
Thanks Scott! I didn’t realize that there’s such a large number of known NPI problems.
I blame it on Wikipedia:
Reading this, it sounded like NPI problems were a rare breed.
Comment #95 November 12th, 2015 at 1:44 am
GI was a problem that, till recently, was not proven to be P time nor quasi P time yet (almost?) all known practical instances of inputs could be solved in P-time.
Are there any such NP-complete problems? Where though we don’t have a P time proof (obviously!) yet in practice known inputs can be solved in P-time.
Any other NPI problems with this characteristic that GI had till now? i.e. No P time proof (yet) but P time in practice.
Comment #96 November 12th, 2015 at 1:59 am
A collected version of the tweets is here: https://storify.com/ptwiddle/babai-s-first-graph-isomorphism-talk if you want to link to this in an addendum it will help people find it better than buried down here.
Comment #97 November 12th, 2015 at 8:14 am
Rahul #94: There are relatively few NPI problems that anyone cares about. But proving P=NP by the strategy you suggest would require solving all the infinitely many NPI problems that no one cares about as well!
Comment #98 November 12th, 2015 at 8:27 am
Rahul #95: Yes, there are NP-complete problems that certain communities consider “efficiently solvable in practice,” using heuristics—k-SAT itself being a prime example! But in every case, this is because those communities care about application domains that tend to produce efficiently solvable instances. If you specifically wanted to produce hard instances, then the very fact that the problems are NP-complete would let you do that, for example by starting with a cryptographic problem (like maybe mining new bitcoins 🙂 ) and then reducing it to your problem. The same is not true of GI.
As for other NPI problems that can be efficiently handled in practice, like GI—I’m straining to come up with a compelling example, but that’s probably just because I don’t know the practical situation for other NPI problems. Maybe algebraic problems (like special cases of polynomial isomorphism), which can be handled efficiently in practice using Gröbner basis methods, for which the only proven runtime upper bound is still exponential? Or maybe the turnpike problem? Anyone else have examples?
Comment #99 November 12th, 2015 at 8:39 am
David #96: Thanks, done!
Comment #100 November 12th, 2015 at 8:42 am
Scott #98:
Thanks. Is it trivial to come up with these reductions?
I mean, sure they are all NP-complete so we can *prove* that such a reduction *exists* but in practice is it known how to algorithmically convert a hard input case of one NP-complete problem to another?
e.g. Say, how do you convert a hard bitcoin mining problem into a hard input for a ksat-solver? (I hope I’m asking a meaningful question!)
Comment #101 November 12th, 2015 at 9:20 am
Rahul #100: Yes, the Cook-Levin Theorem is completely explicit, so it’s known in practice how to do this. You can find code online that will help with this—e.g., ToughSAT by Henry Yuen and Joseph Bebel, or the CNF generator by Paul Purdom and Amr Sabry (these two generate k-SAT instances based on factoring, but you could modify it for bitcoin mining or whatever else you wanted). The main practical issue is controlling the size of the k-SAT instance—i.e., it might be easy to write code for such things that will generate instances with billions of variables, but then you’d need to work harder if you wanted instances with merely millions of variables.
Comment #102 November 12th, 2015 at 9:36 am
Scott #93
If N!=NP, and the NPI set isn’t empty (once we’ve excluded things like GI and factorization, assuming those will eventually fall into P), could there be a connection between all the NP-I problems where one can always be reduced to another in poly time? (just like it’s the case for NP-complete problems)
Comment #103 November 12th, 2015 at 10:18 am
Those looking for more detail than the storify link might enjoy the following post
http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/
Comment #104 November 12th, 2015 at 10:29 am
[…] lelkendezik a felfedezésről Scott Aaronson, a világ legjobb műszaki egyetemei közé tartozó MIT matematikusa. A gráf izomorfizmus […]
Comment #105 November 12th, 2015 at 10:41 am
Scott – “You know what I meant.”
Yes, I do know what you meant, but I’m not sure that I completely agree. I imagine that I mostly agree. However, some of these more complicated theoretical algorithms have a character of “Either X, Y, or Z will work”; for instance, one of Babai’s titles has the phrase “split or Johnson”. When it gets to that point, the focus really is more on a complexity upper bound than on endorsement of a specific algorithm; and you can if you like co-opt any competing algorithm.
Comment #106 November 12th, 2015 at 10:46 am
Rahul #100; For any cryptographic problem, you can draw the electrical circuit that implements it, then reduce it to k-SAT. See the Wikipedia article section on P=NP, section “Consequences of Solution”, for references doing exactly this for DES, AES, and cryptographic hash functions.
Comment #107 November 12th, 2015 at 10:58 am
Thinking about the quasipolynomial time class following Sniffnoy’s comments. It is easy to write down an oracle A such that DTIME(exponentiality 0)^A does not contain NP^A (using the notion of exponentiality Scott used here which I haven’t checked if it is identical to that used for transseries). We can take A to be an essentially “standard” oracle where we for each n we flip a coin and if n is heads A accepts exactly one randomly chosen string of length n and if the coin is tails then A rejects all strings of length n.
We also have that P !=DTIME(exponentiality 0) by the time hierarchy theorem.
I would strongly suspect that DTIME(exponentiality 0) and BQP are incomparable (that is, that neither contains the other) but that would be a statement strictly stronger than the claim that BQP != P, so can we at least find oracles for this? That is, is there an oracle with respect to which DTIME(exponentiality 0) and BQP are incomparable? I don’t see an immediately obvious construction either way.
Comment #108 November 12th, 2015 at 11:09 am
fred #102:
could there be a connection between all the NP-I problems where one can always be reduced to another in poly time? (just like it’s the case for NP-complete problems)
No, Ladner’s Theorem rules that out as well. Assuming P≠NP, it actually gives you infinitely many inequivalent NPI problems (including incomparable ones), in a complicated lattice analogous to the lattice of Turing degrees from computability theory. But before you get too excited, all of these problems will be extremely artificial, basically just SAT hobbled using diagonalization tricks applied in different ways.
Comment #109 November 12th, 2015 at 11:11 am
Joshua #107: It’s easy to construct both of the oracles you want. Firstly, Simon’s problem gives you something that’s in BQP but not in BPTIME(20.499n), so certainly not in BPTIME(exponentiality 0). Secondly, in DTIME(exponentiality 0), you can access parts of the oracle string that the BQP machine can’t even reach. 🙂
Comment #110 November 12th, 2015 at 11:18 am
Scott and Rahul – Scott is of course correct about NP-complete problems. The very definition of a NP-completeness (with Post/Karp reduction) is that the problem includes every other problem in NP in disguise, including bitcoin mining. “Solvable in practice” usually means, in effect, a distributional problem, a problem with a probability distribution on input. Of course, an NP-complete problem can be made easy by choosing an input distribution that makes difficult inputs unlikely.
As for NPI problems with no known hard examples, actually, I know one: Uknottedness. The news this month over graph isomorphism suggests that one day we might see a fast algorithm for determining whether a knot diagram represents the unknot.
Comment #111 November 12th, 2015 at 11:56 am
Is Garey and Johnson’s book on NP-completeness still a good introduction to complexity?
Comment #112 November 12th, 2015 at 12:08 pm
asdf #111: Sure, it’s great for what it covers (I still use it from time to time, when I need to look up who proved some weird problem NP-complete in the 1970s). But of course, if you want to know what’s happened in the last 35 years, you’ll need a newer book, like Papadimitriou, Arora&Barak, or Mertens&Moore.
Comment #113 November 12th, 2015 at 12:45 pm
Looking at the Halting Problem’s undecidability proof i wonder if solvers for NP-Complete problems might require superpolynomial time simply to avoid being embedded into an input and induced in error.
A solver for an NP-Complete problem which receives a function or TM as input would be more susceptible to contradiction if it runs in polynomial time because it allows the input function or TM to use it as a subroutine.
If the solver runs in exponential time, then it’s automatically inaccessible to any input function or TM provided to an NP-Complete problem.
Comment #114 November 12th, 2015 at 1:09 pm
Scott #109,
Ah yes, those are both pretty obvious once you point them out. I should have thought about it longer before asking anything.
(Also on the subject #112, I want to thank you for pointing out Mertens and Moore a while ago. That book is awesome.)
Comment #115 November 12th, 2015 at 2:16 pm
Forgive me my ignorance, I would like to know, if polynomial reducibility leads one to the class of NP-complete problems and the P!=NP Problem, does there exist an analog theory which uses quasi-polynomial reductions?
Comment #116 November 12th, 2015 at 2:36 pm
Scott #108
But then does it mean that it would be enough to show that just one particular flavor of NP-I problem can’t be done better than in sub-exponential time to prove that P!=NP?
Comment #117 November 12th, 2015 at 4:16 pm
anonymous #115 and fred #116: Yes and yes.
Comment #118 November 12th, 2015 at 4:56 pm
Here’s Jeremy Kun’s summary of the first talk.
Comment #119 November 12th, 2015 at 5:23 pm
Scott #117 because you answered with ‘yes’ to my question in comment #115, it immediately comes to mind if a quasipolynomial P != NP variant is easier to solve, or even if their is a whole spectra of these. I searched the complexity zoo for a quasipolynomial NP complexity class but didn’t find any, pointers?
Comment #120 November 12th, 2015 at 5:53 pm
anonymous #119: I’ve never seen anyone study nondeterministic quasipolynomial time, probably just because they haven’t needed it for anything. But sure, you could ask the quasipolynomial variant of the P vs. NP question. If P=NP, then certainly QuasiP=QuasiNP (by padding), but even if P≠NP it would be conceivable that QuasiP=QuasiNP. Thus, separating QuasiP from QuasiNP is formally only harder than separating P from NP (but in practice, it’s probably the same difficulty).
Comment #121 November 12th, 2015 at 6:45 pm
Greg #110: You’re also right, of course, that one could now write a practical GI program that’s also provably correct and quasipolynomial-time, by starting with NAUTY (or whatever), and then falling back on Babai’s new algorithm if NAUTY fails to return an answer within some specified time bound. What I don’t know is whether the latter will return an answer within a practically-acceptable amount of time, in those rare cases where it gets invoked at all. On the other hand, at least from Jeremy Kun’s summary, I don’t see any obvious obstruction to the algorithm being made practically efficient: it’s not like the order of the monster group is hiding in the constant factors or anything like that, as one might have feared a-priori.
Also, thanks for mentioning unknottedness! I thought about it, of course, but I didn’t know that people don’t know how to sample instances that foil the existing algorithms.
Comment #122 November 12th, 2015 at 9:37 pm
Thanks for the link Scott! I appreciate you letting me know if you spot some holes in my understanding, as I’m certain it’s lacking in many respects.
In re point (4), I recall Babai emphasizing that this new result was heavily influenced by relatively recent work (2008) on hypergraph isomorphism with his student Paolo Codenotti. I have not read this paper, so I don’t know how much it relates to what I have absorbed about the problem so far.
See: Babai-Codenotti, Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS’08.
Comment #123 November 12th, 2015 at 10:04 pm
In what sense are Johnson graphs ‘hard’? In some sense they seem to be easy, because there’s no ‘quasi-johnson’ graph to fool you. If two things look like Johnson graphs of the same size, then gosh darn it, they are in fact isomorphic.
Comment #124 November 12th, 2015 at 10:57 pm
Bram #123: I don’t think Johnson graphs aren’t as much hard as that they serve as counterexamples to known approaches. (The Petersen graph, which is the complement of J(5,2) gives graph theorists headaches by serving as a counterexample to otherwise nice conjectures.)
My understanding is that when Babai proved that the Johnson graphs are in some sense the only barrier, then it turned out that this case could also be handled.
Comment #125 November 13th, 2015 at 12:03 am
Interesting. I’m guessing that in the end we’ll have a polynomial-time algorithm for GI, but that it won’t look like a polytime algorithm: It will look like something which throws together a bunch of intuitive heuristics and in cases where things are still tied goes ‘eh, close enough, they’re probably the same’. So it looks like something a hacker came up with which probably has exceptional inputs but because it’s doing exactly the right things then in those tied cases it must be a Johnson graph, so the assumption of equality is valid.
Comment #126 November 13th, 2015 at 2:37 am
Regarding the 30-year gap, I agree that sometimes it just takes an incredibly long time and a brilliant insight or two to achieve even relatively “simple” results that are “obvious” in hindsight…
For example, I remember several years ago at FOCS, Timothy Chan resolved a longstanding open question on the Klee Measure problem with a very simple divide and conquer algorithm. Or Diffie-Hellman, RSA, and AKS primality test all use elementary number theory that would have been well within the reach of, say, Gauss (or at least, his students), had he only been given some context… It makes such results all the more impressive.
Comment #127 November 13th, 2015 at 5:27 am
Had this string isomorphism problem been studied before? Is it perhaps known to be equivalent to graph isomorphism?
Comment #128 November 13th, 2015 at 6:12 am
(1) Does anyone know how NAUTY or other practically efficient algorithms for GI perform on Johnson graphs? There is some tension between “the extreme difficulty of finding hard [GI] instances in practice” and “the Johnson graph emerged over and over as a forehead-bangingly hard case that caused numerous [GI] algorithms to fail.”
(2) On the topic of
Well, for me this is just a practical example of Cook’s theorem on the hardness of theorem proving! Assuming the exponential time hypothesis, even if you have all the pieces of a sizeable puzzle in front of you, it may well take 30 years to come up with a proof that combines all of them in the right way to yield the theorem. 🙂
Comment #129 November 13th, 2015 at 7:45 am
Scott #121: I think maybe you misunderstood Greg’s comment about unknottedness. As far as I understand, it’s not so much that people don’t know how to find hard instances for most of the known algorithms, it’s more that the algorithms simply don’t really have harder-than-average instances and are just inherently more-or-less exponential.
Comment #130 November 13th, 2015 at 7:53 am
Bram #125: There’s a continuum between math and hacking, as much as the more abstractifying mathematicians might hate to admit it—both involve an interplay between deep ideas and case analysis, exceptions, and whatever the hell else is needed to get your thing to work.
Comment #131 November 13th, 2015 at 7:55 am
jonas #127: Were string isomorphism known to be equivalent to GI, I’m sure Laci and Jeremy would have told us as much.
Comment #132 November 13th, 2015 at 9:33 am
Scott and Aula – As I understand it, the issue with both graph isomorphism and unknottedness is sort-of in between what you two have said. (But might simply equal what Scott really meant.) It depends on who moves first. If I produce an algorithm to generate instances of the question, then you can find an algorithm that almost always solves those instances quickly. If I produce an algorithm to solve the problem together with a claimed proof of an upper bound, then you can make instances to contradict the point. (Unless I happen to be Laci Babai in the case of GI…)
The point is that an attempt to make hard instances in these questions always manages to come with a hint for how to solve those particular instances. It’s a deadlock where any new idea by either side gets shot down by the other side.
In the case of unknottedness, the typical thing that’s difficult to beat is a greedy algorithm that uses Reidemeister moves. In fact there has been a dramatic result in recent years, a partial algorithm due to Dynnikov that is not necessarily polynomial time, but that is weakly monotonic in an input complexity measure. Dynnikov’s algorithm considers grid diagrams, which are knot diagrams composed of rectilinear segments in the plane. (I.e., the way that you would draw a knot in an Etch-a-Sketch, turning one knob at a time.) Using an analogue of Reidemeister moves for these, Dynnikov shows that, while the number of crossings might go up or down, the number of grid edges never has to increase, if it’s a diagram of the unknot.
If you can always find a sequence of Dynnikov moves that removes just one pair of edges from a grid diagram in polynomial time (note that this edge number is always even), then you’re done. Even this has an important recent partial result. Lackenby showed that there is a simplifying sequence of Dynnikov moves with polynomial length. He thus showed that a polynomial number of Reidemeister moves suffices to simplify an unknot. This is a dramatic second proof that unknottedness is in NP. (After the first proof due to Hass-Lagarias-Pippenger and Agol-Hass-Thurston, using a disk certificate rather than a sequence of moves.)
Comment #133 November 13th, 2015 at 1:24 pm
” What is it that needed another 30 years? ”
Well Scott I would like to return the question back to the sender: Why, oh why, did it take almost a century to realize that integers could be *physically* factored in polynomial time ? What is it that happened between the emergence of quantum mechanics in 1900 and the magistral algorithm of Shor in 1994 ?
I mean we have known since Fermat’s little theorem the link between period-finding and factorization. In the early 19th century, physicists grasped the nature of waves; diffraction experiments showed that two waves interfere constructively or destructively depending on their spatial periods and phases. The Schrödinger equation tells us that matter interferes very much like waves. So by the end of the 20s, the stage was set. It would not have been anachronic to write a semi-philosophical, rather vague paper as to why the factors of a composite number could be found with some sort of quantum contraption. (Actually I wonder why a polymath like Von Neumann – versed in physics, maths and computer science – did not come up with this)
Maybe mindsets were not ripe. Maybe the right person (Shor) had to be at the right place (Bell Labs) at the right time (the early 90s, after works by the likes of Feynman, Deutsch or Ekert on quantum computing). Maybe we had to wait for the commercial explosion of RSA cryptography and the theoretical unification brought by NP-completeness (or suspected lack of in the case of factorization) to appreciate the practical and theoretical interest in factorizing integers in polynomial time. I do not really know why it took so long. But if the polytime factorability of integers is a fundamental law of nature (as I reckon you have rightly contended), then it feels like we have been quite slow at connecting the dots and finding what nature is capable of.
Comment #134 November 13th, 2015 at 3:09 pm
Anthony #133: Yes, you can absolutely ask the same question about Shor’s algorithm—I’ve often done so myself! In that case, though, it’s easy to think of some partial answers: first, complexity theory (and the polynomial/exponential dichotomy) only came into clear focus in the mid-60s. Second, Diffie-Hellman and RSA (and with them, the tremendous interest in factoring and discrete log) were only proposed in the 70s, and only came into widespread use in the 80s and 90s. Third, in the 80s, theoretical computer scientists had their hands so full understanding the role of classical randomness, that quantum computing might have seemed premature!
With graph isomorphism, part of my question is that it’s not just the same approach people had formulated in the early 1980s—it’s literally one of the same people! So if there’s a clear answer about “what took 30 years,” it’s possible that Laci is the only person on earth who can supply it. (For that reason, I’m grateful for Jeremy’s comment #122.)
Comment #135 November 13th, 2015 at 3:51 pm
[…] to a much lower class.” After MIT associate professor Scott Aaronson heard about Babai’s claim, he blogged that it could be “the theoretical computer science result of the […]
Comment #136 November 13th, 2015 at 4:03 pm
What took 30 years?
Probably something to do with DeLorean time machines, flux capacitors, and Babai meeting himself back in 1985?
Comment #137 November 13th, 2015 at 4:06 pm
Assuming this work is solid… doesn’t it in effect generalize the 5 color map proof to any dimensionality? If any graph can be tokenized as this algorithm suggests, it would seem to me this algorithm defines some sort of absolute limit on the upper complexity of any graph? That would seem a larger breakthrough than GI computational speedup. No?
Comment #138 November 13th, 2015 at 5:55 pm
Randall #137: I don’t know where you got the idea that the work does any of those other things. It solves graph isomorphism (and more generally, string isomorphism) in quasipolynomial time.
Comment #139 November 13th, 2015 at 6:58 pm
Randall #137: Assuming I’ve understood you correctly — literally any finite graph can be embedded in R³, so there’s no higher-dimensional analogue of the 4-color theorem.
Comment #140 November 14th, 2015 at 3:40 pm
Randall #137,
To expand on Sniffnoy’s comment, the correct generalization of the 4-color theorem is not to generalize the number of dimensions but rather to generalize the surface one is drawing the map (or graph) on. So for example, genus one is a torus (the surface of a donut) and it turns out that one needs 7 colors to color any map on a donate and this is really best possible since it is possible to embed K_7 on a torus. Here K_7 is the the graph of 7 vertices where each vertex is connected to all the other vertices. Similar results exist for higher genus. In this context, the four color theorem becomes a statement about coloring a graph on the sphere. Curiously, the higher genus cases are actually much easier than the genus zero case.
The other major direction to generalize the four color theorem is the Hadwiger conjecture https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)
None of these though have much to do with Babai’s result at all.
As to the idea that Babai’s result says that graphs are in some sense not that complicated, I’m not completely sure, but I’d point out that the isomorphism problem of integers is pretty trivial, but I’m not sure one would see that as meaning that integers are not complicated.
Comment #141 November 14th, 2015 at 6:50 pm
@Jushua #140
What is the result for a 3D region where we consider volumes as touching along planes but not lines or points?
Comment #142 November 15th, 2015 at 12:29 am
Rahul: I don’t think that’s any different from asking about colorings of graphs embedded in R³.
Actually, here’s a possible higher-dimensional generalization. One can consider colorings of hypergraphs (a proper coloring being one that doesn’t make any edge monochromatic). Let’s suppose that the largest edge has k vertices. Then you could ask whether a given such hypergraph can be embedded in R^(k+1). (I’ll define this as follows: Make an abstract simpicial complex by considering all subsets of edges, we’ll say the graph is embeddable if the simplicial complex is.)
So then you could ask the question of whether knowing that a hypergraph, with largest edge having k vertices, being embeddable in R^(k+1), gives you an upper bound on its chromatic number, and what that might be. I don’t know anything about this problem — I’m going to assume somebody must have studied this before, but I don’t know what the terms to search on are.
(But again none of this is relevant to Babai’s result!)
Comment #143 November 15th, 2015 at 4:46 am
Wait, sorry, the problem is silly as I stated it. (Because, e.g., take a graph, embed it in R³, then add any number of (irrelevant) edges of cardinality 3.) So let’s make the additional assumption that the hypergraph is actually k-uniform (i.e., all edges have cardinality k). That one might actually be nontrivial.
Comment #144 November 15th, 2015 at 5:04 am
Oops, sorry for the triple post, but obviously my last two posts contained an off-by-one error; I meant R^k, not R^(k+1). I got the cardinality of an edge (k) confused with its “dimension” (k-1).
FWIW, here’s a first naïve guess: The largest complete k-uniform hypergraph in R^k should have k+2 points (k+1 making a simplex, 1 in the center). In the case k=2, where this makes a K_4, this is actually the most colors you ever need (though obviously proving this is very hard!). If that were to be true in general, then the number of colors in general would be given by ⌈(k+2)/(k-1)⌉. (Since if each edge has k points, you can have up to k-1 points of each color.) This returns 4 for k=2, 3 for k=3, and 2 if k≥4.
Something tells me that’s probably not right. But that’s what would be true if a complete graph maximizing the number of colors needed were to extend beyond the case k=2.
Comment #145 November 15th, 2015 at 8:11 am
@Rahul #141,
That doesn’t make a difference. Replace each vertex with a thick sphere and each edge becomes half of a thickened bendy rod (a tentacle with a flat tip if you prefer) attached to the sphere, so the each region meets each other relevant region in part of plane.
Comment #146 November 15th, 2015 at 9:14 am
Sniffnoy: any finite hypergraph can be embedded in R³. Since it’s pretty easy to construct such an embedding, I’ll describe it here. A vertex V_i has a point at (i, 0, 0) and an edge E_j has a point at (0, j, 1) and if E_j contains V_i then there is a path that goes from (i, 0, 0) via (i, j, 0) and (i, j, 1) to (0, j, 1) in such a way that it doesn’t cross any other path. This construction even works for countably infinite hypergraphs.
Comment #147 November 15th, 2015 at 1:33 pm
Sniffnoy,
Your comments incidentally bring up a related question: how difficult is hypergraph isomorphism? My suspicion is that it is reducible to graph isomorphism, but an immediate reduction doesn’t jump out to me.
Comment #148 November 15th, 2015 at 2:18 pm
Unless I’m missing something, that’s a different sort of embedding than I’m talking about? I’m talking about first forming a simplicial complex by taking all subsets of edges, and then embedding that in R^k in the usual sense. So e.g. if you took a triangulation of a Klein bottle, and made a hypergraph by taking the vertices as vertices and the faces (triangles) as edges, that wouldn’t embed in R³ in the sense I’m talking about. Unless I’m missing something?
Comment #149 November 15th, 2015 at 3:42 pm
Scott is Group isomorphism in coNP known? It is unknown whether Graph isomorphism in coNP right? Is it known one implies another or vice versa? Is there a reference?
Comment #150 November 15th, 2015 at 4:18 pm
Arul #149: Group isomorphism easily reduces to graph isomorphism (and it has a trivial nlog(n) algorithm—no need for Babai’s breakthrough!). But neither group isomorphism nor graph isomorphism is currently known to be in coNP—or not without a derandomization assumption, like coNP=coAM. Sorry, I don’t know a good reference offhand; try googling.
Comment #151 November 15th, 2015 at 4:36 pm
The one subtlety of hypergraph isomorphism is that there are exponentially many available hyperedges. Let’s set that aside and consider the hypergraph data type to be a vertex set and a polynomial-length list of hyperedges. It is easy to convert such a hypergraph H to a bipartite graph B: The blue vertices of B are the vertices of H, the red vertices are the hyperedges, and there is a connecting edge when the corresponding hyperedge of H contains the corresponding vertex of H.
It is also easy to reduce bipartite graphs — or colored graphs in general — to isomorphism of uncolored graphs. For instance, you can tag every red vertex with one leaf and every blue vertex with two leaves.
You can also reduce isomorphism of directed graphs to isomorphism of graphs with three colors of vertices by making the original vertices green, and changing each edge to a path of the form green-red-blue-green. In the end, many different questions reduce to isomorphism of uncolored, undirected, simple graphs. That’s part of the appeal of the question, and actually it’s essential to reflexively switch between these different guises in order to look for good algorithms.
Comment #152 November 15th, 2015 at 4:39 pm
Joshua,
yes, hypergraph isomorphism reduces to GI. From a hypergraph, form a bipartite graph, with one class of vertices the faces and the other the vertices.
Comment #153 November 15th, 2015 at 7:43 pm
Are there any summaries of Babai’s second lecture?
Comment #154 November 16th, 2015 at 8:11 am
This suspense & mystery is kinda annoying. I wish Babai had released a manuscript at least right after his first talk!
And big boo Univ. of Chicago, for letting such an important discovery pass by without a live stream of the lectures, hell, not even a video released even today a week after the first talk.
PS. There’s still some small chance the proof has a bug right?
Comment #155 November 16th, 2015 at 9:02 am
Sniffnoy #148: It’s certainly possible to map hypergraphs to simplical complices like you suggest, but most people wouldn’t want that map as a part of anything they would call an embedding, because the map is not one-to-one; for example, if {A, B, C} is an edge of a hypergraph, the map loses information about whether any of {A, B}, {A, C}, {B, C}, {A}, {B}, {C} are also edges (they must all be part of the simplical complex by definition). Specifically, you certainly don’t want to use that map to determine the coloring number of a hypergraph, because it will very likely increase the necessary number of colors (or, if you insist that even the one-vertex edges must not be monochromatic, the map makes all hypergraphs uncolorable).
Comment #156 November 16th, 2015 at 7:02 pm
OK, but I already explicitly required that the hypergraph was k-uniform, in which case the map doesn’t lose information.
Comment #157 November 16th, 2015 at 9:38 pm
A video of the first talk has been posted on Prof. Babai’s home page.
Here’s a direct link: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
Comment #158 November 16th, 2015 at 10:14 pm
Update: Laci’s talk is now online: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
Comment #159 November 17th, 2015 at 3:30 am
The first talk is now online
http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
Comment #160 November 17th, 2015 at 4:18 am
The video of the first talk is now online.
Comment #161 November 17th, 2015 at 9:39 am
Scott #117
“yes”
(answering “it would be enough to show that just one particular flavor of NP-I problem can’t be done better than in sub-exponential time to prove that P!=NP?”)
It’s just strange that we haven’t proven any (worst case) lower bound yet on anything that’s slower than polynomial.
E.g., for sorting, n Log(n) has been proven to be the best lower bound, no? (using certain assumptions)
Comment #162 November 17th, 2015 at 10:44 am
Scott #10: “But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it.”
What’s the order in practice? Is it “basically in O(n)” or “basically in O(n^2)” or something else?
Comment #163 November 17th, 2015 at 5:03 pm
There is no good answer to that question, because there is more than one way that these algorithms are used in practice. For instance, I think that the first-level canonical recoloring algorithm (Weisfeiler-Lehman) works in quasilinear time in the number of edges of the graph, and that will work for a lot of people. It works for random graphs and it works for trees, for instance. It’s also a lot simpler than the full strength of NAUTY. Other people might need graph isomorphism to distinguish Hadamard matrices (say), and that case is harder.
Since the concept of “in practice” is a moving target (in practice 🙂 ), it shows you the value of proving a rigorous, worst-case bound.
Comment #164 November 19th, 2015 at 12:56 pm
Off-topic, but any comment on the latest heavy breathing from Google and D-Wave? Faster than the Universe? And we’re forced to wait twenty days.
http://9to5google.com/2015/11/11/google-planning-a-watershed-quantum-computing-announcement-december-8/
Comment #165 November 20th, 2015 at 1:27 am
Gentzen #153, the second GI lecture is on November 24, next week. There was a lecture on the 12th about the group theory used in the GI solution, but I think it’s more expository. See:
http://people.cs.uchicago.edu/~laci/quasipoly.html
Comment #166 November 20th, 2015 at 12:06 pm
[…] 7. Shtetl-Optimized » Blog Archive » G. Phi. Fo. Fum. […]
Comment #167 November 20th, 2015 at 1:09 pm
Greg, Scott:
Any thoughts on whether this string automorphism algorithm will lead to more progress on the Dihedral Subgroup Problem?
Comment #168 November 21st, 2015 at 1:26 pm
Nick Mann #164
WTF does “faster than the universe” even mean? I’m confused.
Comment #169 November 21st, 2015 at 2:23 pm
Stephen #167: I don’t see a relationship, though of course that’s not a proof that there isn’t one! With graph and string isomorphism, you tend to have a lot more structure to work with than with the nonabelian HSP (which is a black-box problem).
Comment #170 November 21st, 2015 at 10:07 pm
Stephen – Hidden subgroup problems and, more generally, hidden stabilizer problems are technically speaking the same type of question as string automorphism and string isomorphism. However, the rules are very different. A hidden stabilizer problem is a case of string automorphism in which (a) the string has exponential length and is accessed through a query model, but (b) the order of the group acting is only single exponential rather than doubly exponential. If the group acting were doubly exponential in size, then basically it would be string automorphism with exponential-sized input. Instead, with the variant rules of hidden subgroup problems, there is no polynomial-time classical algorithm — because the input is too large for that to be possible. On the other hand, by the magic of querying the input in quantum superposition, there can be a quantum polynomial time algorithm.
In the specific case of the *dihedral* hidden subgroup problem, the group acting is so restricted that Babai’s work is not needed to understand it. At this point, so many rules have changed that it’s not the same question at all. It’s a bit ironic, because dihedral hidden subgroup is the same as hidden shift, and that’s much truer to the name “string isomorphism” than what string isomorphism actually means in Babai’s context.
With some other hidden subgroup problem, especially for the symmetric group, it is conceivable — but not particularly forseeable — that Babai’s work would have some influence. Again, there are enough key differences that it’s just not the same question.
Comment #171 November 22nd, 2015 at 2:54 am
So has there been any more analysis of the lecture contents online, or is everyone waiting for the second lecture and/or the preprint?
Comment #172 November 22nd, 2015 at 9:03 pm
Isn’t Graph Isomorphism more directly related to the Hidden Subgroup Problem for the symmetric group (than the dihedral group)? At least I was under the impression that a fast (quantum) algorithm for the symmetric group would yield a fast algorithm for graph isomorphism.
Comment #173 November 23rd, 2015 at 1:02 am
Nick Mann #164: Just when Scott thinks he can talk about something he is really interested in, D-Wave resurfaces. Poor guy.
From the graph, it appears D-Wave should be “faster than the Universe” by sometime in 2015. That should be real soon now!
Comment #174 November 23rd, 2015 at 3:26 am
Would a result such as GI is in P/Poly or factoring is in P/Poly get a tenure in MIT or at least a PhD in MIT?
Or are these risky problems only suitable for tenured faculty?
Comment #175 November 23rd, 2015 at 8:45 am
If they are indeed faster than the Universe methinks they need a new, bolder name than boring “DWave”!
Comment #176 November 23rd, 2015 at 10:28 am
a #174:
Would a result such as GI is in P/Poly or factoring is in P/Poly get a tenure in MIT or at least a PhD in MIT?
Yes.
Or are these risky problems only suitable for tenured faculty?
It’s always high-risk to work on something big, but that doesn’t mean only tenured faculty can do it. I recommend a diversified portfolio.
Comment #177 November 23rd, 2015 at 11:38 am
That’s correct, but despite initial hopes, I and many people have long been in the camp that this is doing things the hard way. The symmetric-group hidden subgroup problem gives you both the dihedral hidden subgroup problem and the graph isomorphism problem, and a lot else besides; and it simply looks much harder than all of these applications.
The only good news about this problem is that a quantum computer can steal the question from the oracle, i.e., there is a quantum algorithm with low query complexity. But after that, no one has any ideas beyond using some version of Grover’s algorithm; and Grover’s algorithm is simply the quantum version of exhaustive search.
Comment #178 November 23rd, 2015 at 11:56 am
Even in this day and age, even a 20-year-old college senior can solve a celebrated open problem posed by one of the most distinguished mathematicians in the world. So, really, there is nothing under the sun that is only suitable for tenured faculty. A faculty position, with or without tenure, is just a job. It is not in and of itself permission to do research, permission which is never strictly needed anyway.
What is true is that a problem is only suitable for those people who actually understand the question. Not just the stated terms of the question, although that is important; but more deeply, what part of the question is the hard part.
It is also true that undergraduates who solve major open problems might well get tenure sooner rather than later.
Comment #179 November 23rd, 2015 at 5:01 pm
“Faster than the universe”… Oh my! Did they mean “bigger than light”?
Comment #180 November 24th, 2015 at 10:53 am
Sorry, continuing the hypergraph coloring angle, because why not:
Some searching yielded this paper, which discusses upper and lower bounds on the number of colors needed to color a k-uniform hypergraph embedded in R^d in a linear manner. This is more strict than just a PL-embedding (let alone a general topological embedding) but that won’t be relevant here.
Table 1 and table 2 give some of their lower and upper bounds, respectively; note that in order for the table to make sense they allowed dependence on n, the number of vertices.
Focusing on the case when d=k, what’s notable is that for k=3, they showed that you may indeed need arbitrarily many colors. So my suggestion above that you might only need 3 colors is certainly false.
However this does leave open the possibility that there might still only need a bounded number of colors for any k which is greater than 3. Oddly their table lists the lower bound as 1 rather than 2; more generally, when k-1≤d≤2k-4 there seems to be this mistake. Hopefully that’s the only mistake!
Anyway, if that paper is still the best known, then certainly no such upper bound is known for any k>2, as their upper bounds there (which work for PL-embeddings too) all depend on n. (Specifically, it’s O(n^(1-1/(k-1))). Or see theorem 18 if you want the constant.) And if you want general topological embeddings rather than PL ones, well, then I guess nobody’s done that (unless somebody has). These are the same when k≤3, apparently, but I’m talking about k>3 right now.
The paper does also mention a conjecture of Gundert and Kalai which would imply a stronger upper bound, but still not a constant one.
(One caution on reading this paper: Theorems 18-22 use the variable “d” for a variable that should really be called “k”, to be consistent with the rest of the paper.)
Comment #181 November 25th, 2015 at 6:13 pm
Any reports yet about lecture #2, which was scheduled for yesterday? There’s an entry about the algorithm on RJLipton’s blog, but no updates about the second lecture.
https://rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm/
Comment #182 November 27th, 2015 at 10:28 pm
Is there a manuscript yet?
Comment #183 December 6th, 2015 at 9:29 pm
[…] to a much lower class.” After MIT associate professor Scott Aaronson heard about Babai’s claim, he blogged that it could be “the theoretical computer science result of the […]
Comment #184 December 9th, 2015 at 2:37 am
If GI turns out to be NP complete does that mean we will be living in heuristica in Impagliazzo’s five worlds? What I mean by this is there are already good heuristics which work very well and finding an hard instance is tough. So if $3SAT$ reduces to $GI$ then most cases of $3SAT$ are easy except a few rare instances?
Comment #185 December 9th, 2015 at 11:04 pm
One of the more interesting developments in graph isomorphisms post the Luk’s et al work of the 80s was that a lot of approaches to solve the problem ran up against the obstacles Cai, Furer, and Immerman and cellular algebras. Does anyone have a good picture of how the new algorithm works from the point of view of this obstacle and cellular algebras?
Comment #186 December 10th, 2015 at 10:02 pm
Dave #185: what do you mean “cellular algebra”? Is that the Graham-Lehrer sense?
Comment #187 December 11th, 2015 at 9:17 am
[…] Por supuesto, si quieres algo más divulgativo, mejor Adrian Cho, “Mathematician claims breakthrough in complexity theory,” News, Science, 10 Nov 2015; Lance Fortnow, “A Primer on Graph Isomorphismm,” Computational Complexity, 12 Nov 2015; Tom Simonite, “Claimed Breakthrough Slays Classic Computing Problem; Encryption Could Be Next,” MIT Technology Review, 13 Nov 2015; y Scott Aaronson, “G. Phi. Fo. Fum.,” Shtetl-Optimized, 12 Nov 2015. […]
Comment #188 December 14th, 2015 at 2:04 pm
The paper is on the arxive!! http://arxiv.org/abs/1512.03547
Comment #189 December 14th, 2015 at 6:05 pm
Does this give us more hope for finding a fast algorithm for the subgraph isomorphism problem, that is, deciding whether a first input graph is isomorphic to a subset of a second input graph?
Comment #190 December 16th, 2015 at 3:40 pm
No comments about the preprint yet?
Comment #191 January 5th, 2016 at 4:42 am
According to Babai’s website, there was a talk on 12 November 2015 on the group theory behind the graph isomorphism problem. Is there a video of this talk anywhere online?
Comment #192 January 5th, 2016 at 7:43 pm
[…] time (2 to a polylog). Other theory blogs have already commented on this (GLL,In Theory,Shetl-Opt)When I was in Graduate School (early 1980's) it looked like GI would get into P. Three key […]
Comment #193 January 8th, 2016 at 10:30 pm
[…] be able to put the pieces together the way that Babai did.More on Babai and graph isomorphism from Scott, Luca, Bill, Tim, Dick and Ken, Reddit, Science News, New Scientist and Science.Read […]
Comment #194 January 31st, 2016 at 10:37 am
[…] mother’s maiden name is Babai.) You can read about it here (and the next three posts) and here. Another is the solution by Jean Bourgain, Ciprian Demeter, Larry Guth of Vinogradov’s main […]