Algorithm Solves Graph Isomorphism in Record Time (2015)

https://www.quantamagazine.org/algorithm-solves-graph-isomorphism-in-record-time-20151214/

by howard941 • 7 years ago

212 73 7 years ago

quantamagazine.org

wolfgke3• 7 years ago

(2015)

aDfbrtVt2• 7 years ago

Technically 2017 was the latest update to the paper, but still not as groundbreaking as the submission title.

aDfbrtVt2• 7 years ago

Here's the updated paper with some significant corrections http://people.cs.uchicago.edu/~laci/upcc-fix.pdf

chmod775• 7 years ago

Those are just the corrections, not the full paper.

dmix• 7 years ago

This is the full paper the OP was referring to: http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf

The fixes linked above are mentioned in the WARNING below the abstract and explained at 18.1.

svat3• 7 years ago

There's an expository paper by Harald Helfgott that goes into earlier work, more foundational stuff, etc — even has exercises: https://arxiv.org/abs/1710.04574

(Originally presented for the Bourbaki Seminar, so not exactly for the non-mathematician, but has more context than reading the paper directly.)

zemptime• 7 years ago

On page 2, in the "coherent configuration" section, what does the x with the - through it mean? I haven't been able to search my way to an answer

kzrdude• 7 years ago

Is the algo practical, implemented by say major generic graph libraries?

sischoel4• 7 years ago

No, graph libraries usually relay on some variation of VF2 and maybe (but I haven't checked) in some cases on the more complicated nauty/traces algorithms.

CJefferson2• 7 years ago

(basically speaking) no-one does Graph Isomorphism with VF2, they use (as you say) Nauty, or some system which derives from that.

Things like VF2 can be used for sub-graph isomorphism (and various variants of that problem). Nauty (and this paper) are useless for solving that problem.

I work in this area, and it's interesting (to me at least) that you would imagine the algorithms for graph isomorphism and sub-graph isomorphism would be quite similar and they really aren't.

rsp19842• 7 years ago

even small graphs can be made to look very different just by moving their nodes around

I'm curious: for the graph isomorphism problem, how are the graphs defined then? It seems there must be a geometric component in there because if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same, wouldn't it?

DominikPeters• 7 years ago

Graphs are given as abstract sets of vertices and sets of edges (as adjacency lists or matrices). The problem is that corresponding vertices in the two graphs may not have the same label, so to solve graph isomorphism naively, one would need to try all n! possible bijections between the vertex sets (where n is the number of vertices).

sischoel4• 7 years ago

Wikipedia has a nice picture of two graphs that are isomorph: https://en.wikipedia.org/wiki/Graph_isomorphism.

It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.

rsp19842• 7 years ago

Thanks much for the clarification. I didn't know that one was "allowed" to change labels. It makes sense now.

TuringTest• 7 years ago

Not if the number of nodes is high, no. The complexity of the naif algorithm grows exponentially, making it unmanageable very fast.

In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph.

This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.

Someone• 7 years ago

”It seems there must be a geometric component in there”

No, there isn’t.

”if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same”

No, it isn’t, unless you know a novel argument that hasn’t been thought of yet by mathematicians.

It is fairly simple for graphs with very few vertices or very few edges, but in general, it isn’t easy at all.

sdenton4• 7 years ago

You might say that it's easy in general (since all but a handful of isomorphism classes are easily distinguished), but hard in full generality. :)

stephencanon• 7 years ago

The problem is to show that the graphs are the same or different up to relabeling of the vertices. I.e. the graphs

    0-1-2     0-2-1

are the same if you swap the labels 1 and 2. You could try to brute force it by trying all possible permutations of vertex labels, but there are n! of those to try, so that doesn't help much. Any polynomial-ish algorithm would need to do something clever that takes advantage of the structure of the problem.

ggggtez2• 7 years ago

A graph is defined as it always is. A set of edges that connect nodes by their IDs. We can use this arrow notation for convenience. Imagine you have a graph: a->b b->c c->d d->b

Is that the same as this graph? a'->b' b'->c' c'->a' d'->a'

You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result.

There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.

vignesh_m• 7 years ago

Its actually pretty hard for even humans to eyeball a graph and figure it out. For example, the wiki article on the peterson graph (https://en.wikipedia.org/wiki/Petersen_graph) has a few drawings that you cant easily say are the same graph.

skunkworker• 7 years ago

"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. "

"Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems."

(exp((log n)^O(1)))

Interesting that there could be a much more varied landscape than was previously thought.

mehrdadn14• 7 years ago

One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial and exponential complexities are given such special status. It's just taken for granted that polynomials and exponential are the 2 classes you care about... with no explanation as to why the rest aren't interesting.

EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.

kevinventullo• 7 years ago

I think it's just that many natural algorithms happen to have polynomial time complexity, since it's basically the complexity of iterated loops. Same with logarithms.

dragontamer2• 7 years ago

Because O(e^x) > O(x^n), for all Integer values of "n".

So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function.

In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial.

Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.

sischoel4• 7 years ago

The class of polynomial time algorithms is closed for some things, that you often see in algorithms: - If you run two polynomial time algorithms in parallel, the result is a polynomial time algorithm again. - If one operation of a polynomial time algorithm, is calling another polynomial time algorithm, then the result runs in polynomial time again.

ivanbakel• 7 years ago

Because polynomial complexity is the measure of what makes a tractable problem [1]. If the question is why - there's no formal reason. Tractability is really just subjective human standards: even high-degree polynomial time is often considered to not enough for a solution to be worthwhile computing.

[1][https://en.wikipedia.org/wiki/Cobham%27s_thesis]

yorwba• 7 years ago

Polynomials are convenient because they allow you to mostly ignore the details of the underlying model of computation. E.g. if you try to simulate a multi-headed Turing machine with a single-headed one, you'll spend a lot of time moving between different positions on the tape, increasing the runtime complexity by a polynomial factor. By considering all polynomials as essentially equivalent, you can choose whichever abstraction you want without having to think too hard about the overhead it adds. That's of course bad if you actually want to implement the fastest algorithm, but it makes proving (and stating) theorems a lot simpler.

jimhefferon• 7 years ago

When you start listing algorithms, you see that their speeds fall in a line. There are the log ones, the polys (with n lg n between n and n^2), the exponentials, and higher.

So why the distinction between poly and exp? A modern computer runs at about 10 GHz, 10,000 million ticks per second, and there are about 3.16×10^7 seconds in a year. Suppose your problem has size n=100. Then an n^3 algorithm takes 3.17×10^{-12} years. A 2^n algorithm takes 4.02×10^{12} years. The first is perfectly practible, the second is not (its time is longer than the age of the universe).

wolfgke3• 7 years ago

One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial complexities are given such special status. It's just taken for granted that polynomials are the class you care about... with no explanation as to why.

The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for.

Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.

MaxBarraclough• 7 years ago

Good lord! Reply after reply after reply that simply refuse to speak to the question you asked!

You're quite right that complexity theory takes us to a hierarchy far richer than simply polynomial and exponentiation [0]. Your question about the emphasis on those two in particular, is a good one. Might be worth submitting on cs.stackexchange.com as a 'soft question'.

[0] https://en.wikipedia.org/wiki/Time_complexity#Table_of_commo...

xorand• 7 years ago

Well in mathematics there is a somewhat similar phenomenon concerning the growth of finitely generated groups. If you have a finitely generated group, pick a generating set as an alphabet and a natural n, then ask how many elements of the group you can build by using only words of length at most n. This is the growth function, whose growth does not change if you pick another generating set.

See [1] the Tits alternative which implies that if your group is linear (huh) then the growth function is either polynomial or exponential. Then there is a result by Gromov [2] which says that if the growth is polynomial then the group is virtually nilpotent. There was a long standing question if there exist finitely generated groups with an intermediate growth and the first example was found [3].

So it's not interesting until it becomes interesting due to a newly discovered fact.

[1] https://en.wikipedia.org/wiki/Tits_alternative

[2] https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_o...

[3] https://en.wikipedia.org/wiki/Grigorchuk_group

abdullahkhalids• 7 years ago

I think the answer is much more trivial than you think. Polynomials and exponential complexities are given such special status simply because when we start classifying "natural" problems, many of them either fall into one of these classes, and not many in the intermediate classes. If they fell into polynomial and sub-exponential time, computer science text books would have chapters dedicated to these two instead. At the end of the day CS is used to make building technology easier and so computer scientists naturally interested in "natural" problems and not artificially designed problems.

Now, why "natural" problems so easily fall into these two categories and not others is a different mystery and not what you asked.

nwallin• 7 years ago

Why am I not taught a single algorithm whose complexity is between these? is my question.

Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2.

There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step."

It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.

svat3• 7 years ago

You may like reading Scott Aaronson's P vs NP survey (2017), which may answer some of your questions about complexity theory: https://www.scottaaronson.com/papers/pnp.pdf

In particular, the section relevant to your question is "1.2.2 The Polynomial-Time Objection" on page 7, quoted in full below:

Objection: But why should we draw the border of efficiency at the polynomial functions, as opposed to any other class of functions—for example, functions upper-bounded by n^2, or functions of the form n^((log n)^c) (called quasipolynomial functions)?
Response: There’s a good theoretical answer to this: it’s because polynomials are the smallest class of functions that contains the linear functions, and that’s closed under basic operations like addition, multiplication, and composition. For this reason, they’re the smallest class that ensures that we can compose “efficient algorithms” a constant number of times, and still get an algorithm that’s efficient overall. For the same reason, polynomials are also the smallest class that ensures that our “set of efficiently solvable problems” is independent of the low-level details of the machine model.
Having said that, much of algorithms research is about lowering the order of the polynomial, for problems already known to be in P, and theoretical computer scientists do use looser notions like quasipolynomial time whenever they’re needed.

To add a couple of points of my own:

- We need to consider at least polynomial functions, for the closed-ness reason (though in practice the exponent is usually small), and superpolynomial functions (in the theoretical/asympotic sense, slower than any polynomial, even n^100000 or whatever!) are already slow enough not to be considered efficient. For that matter do you learn any single exponential algorithm in (say) an undergraduate course? If you're in an area where exponential algorithms are of interest though, then it's not actually unusual to study sub-exponential (and superpolynomial) ones, as those are the most efficient we have.

* There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Factoring could be taught though, if the students are all interested in number theory I guess. When I took a course on "algebra and computation" (problems in group theory etc), we did encounter quite a few such algorithms.

gnull• 7 years ago

That's exactly how I felt about polynomial time definition when I was just starting to study complexity theory. Now, after a two year complexity-focused master program, I realized a few things which changed the way I perceive it:

1. P is a roughly approximate definition of «feasible» problems.

P doesn't perfectly capture problems we intuitively understand as feasible (e.g, P includes problems which are solved in O(n^10000) time), but it is good in other respects: its definition is independent of computation model (but the model has to be able to simulate a Turing machine with at most polynomial slowdown, which is true for all reasonable models); P has complete problems; P is closed under many ways of combining algorithms (e.g. if you run a poly-time algorithm poly times, what you get is also a poly-time algorithm). So P isn't perfect way to define feasible problems, but it's good enough (or maybe the best we have?).

There may exist other ways to formalize feasible computations, which could fix P's drawbacks. Maybe complexity theorists will come up with one later, when they get a better understanding of computations. But until then, they work with what they've got.

2. Even if you don't buy all this «feasibility» interpretation, P will still make perfect sense for theory. Especially, when you ask questions about its relation to other classes.

It is natural for computer scientists to consider variations of some computation model and try to understand which of those variations are stronger and how much stronger they are. For example, randomized and nondeterministic Turing machines are variations of usual deterministic Turing machine (DTM). But the former two have their own unique superpowers, which are randomness and nondeterminism. But how powerful these superpowers are? Can a DTM provided with such a superpower solve more problems? And if so, can we compensate the DTM's lack of superpower by providing it more running time? How much time would suffice for that?

In these terms we can say, that P-vs-NP question actually asks whether polynomial-time DTM's lack of nondeterminism can be compensated by allowing it to run poly(n) times longer. Similarly, if you ask the same question but with «randomness» instead of «nontereminism», you will get another famous problem of P-vs-ZPP (or P-vs-BPP, depending on your definition of randomness).

Computer scientists asked similar questions for models other than Turing machine, and successfully answered them. For example, for finite automatons we already know how many extra states we need to go from nondeterministic to deterministic one. Similarly, for communication complexity we know something about the relation between nondeterministic, deterministic, and randomized complexity.

EDIT: Ooops, I replied to the original version of your post, before you clarified what you meant.

ggggtez2• 7 years ago

(2017). This is old news, I thought for a moment he had a new paper. Please add the year.

howard941• 7 years ago

jmmcd• 7 years ago

Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence" for what complexity class the problem is in.

mpoteat• 7 years ago

Unfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.

nine_k• 7 years ago

Likely it's the lower bound (of something) that an important conjecture in the paper gives? That is, it's not some new kind of a lower bound, but a way to refer to it?

evrydayhustling• 7 years ago

100% this. One of the cleanest descriptions of key insights and broader scientific landscape ("glide path" from quasipolynomial to P) I have seen. Erica, if you are seeing this, nice work and I'll be watching for more.

dbchiem• 7 years ago

Absolutely, I think the author did a magnificent job!. Reading the article, all the intricacies (P/NP, polynomial/exponential, blind test, graph coloring) are quite clear and easy to comprehend.

Here are some gentle articles on the zero-knowledge in case anyone is curious:

https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

https://blockgeeks.com/guides/what-is-zksnarks/

meuk• 7 years ago

Agreed! I was already prepared to be annoyed by sketchy metaphors that didn't quite make sense, but this was delightful and very informative to read.

B3QL• 7 years ago

Explanation of the current state of review: https://cstheory.stackexchange.com/a/40373

penguin_booze• 7 years ago

"Monads are monoids in the category of endofunctors. What's the problem?" -- that's how every paper looks at me!

Algorithm Solves Graph Isomorphism in Record Time (2015)

Related Stories