{\huge Isomorphism Is Where It's At}

Isomorphism at the SODA 2014 conference \vspace{.5in}

Ronald Read and Derek Corneil are Canadian mathematicians and computer scientists. Read earned a PhD in Mathematics from the University of London in 1959, while Corneil was one of the inaugural PhD's in the University of Toronto's Department of Computer Science. Read is also an accomplished musician and composer---indeed our photo comes from his entry with a sheet-music publisher in England---and here is a music-themed paper. Corneil became Chair at UT DCS and has done much liaison work with Canadian IT companies and international education. Together they wrote a survey paper in the 1977 first volume of the Journal of Graph Theory titled ``The Graph Isomorphism Disease.''

Today Ken and I would like to take issue with one of the words in their title. No, not ``disease,'' but rather: ``graph.''

The graph isomorphism (GI) problem itself has a long history, and already did in the 1970s. The computational problem is to determine whether two given adjacency matrices (or edge lists) of graphs in fact represent the same graph, and has considerable practical importance. The theoretical problem is whether GI has a polynomial-time algorithm; GI is in $latex {\mathsf{NP}}&fg=000000$ but has ``intermediate'' status of not being classified as either $latex {\mathsf{NP}}&fg=000000$-complete or in $latex {\mathsf{P}}&fg=000000$. In the 1970's there seemed to be great progress toward the latter, as algorithms were obtained for graphs of bounded degree, and later, bounded multiplicity of eigenvalues of the adjacency matrices. But this ground to a halt, and GI has even resisted huge efforts recently to classify it into bounded-error quantum polynomial time ($latex {\mathsf{BQP}}&fg=000000$), even though $latex {\mathsf{BQP}}&fg=000000$ contains another of the few and famous intermediate problems, factoring. The problem's seduction and nettlesomeness led Read and Corneil to classify it as a mathematical disease.

Happily this disease has been manifesting itself in different forms that recently seem amenable to being ``cured'' by real progress. The list of accepted papers to the upcoming SODA 2014 conference has several instances:

• Lattice Isomorphism: a paper by Ishay Haviv and Oded Regev.
• Order-Type Isomorphism: a paper by Greg Aloupis, John Iacono, Stefan Langerman, \"Ozgür \"Ozkan, adding Stefanie Wuhrer.
• Robust Graph Isomorphism, an approximation concept developed by Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou.

None of these directly targets GI or its main spinoff, group isomorphism. Still, the range of interesting and applicable isomorphism-type problems is expanding in ways we appreciate. But first some words about the originals.

Graph and Group Isomorphism

Unfortunately, one of us---that is I, Dick---have spent more hours then I care to admit, working on these two isomorphism problems. Ages ago with Zeke Zalcstein---and independent from Bob Tarjan---I made the trivial but useful observation that group isomorphism can be solved in time $latex {n^{\log n +O(1)}}&fg=000000$. Here the group must be presented as a multiplication table. David Rosenbaum has shaved down the exponent by one or two factors of $latex {\frac{1}{2}}&fg=000000$ as we covered last spring, including a paper at SODA 2013. Just as we go to press---well to Wordpress---Josh Grochow has posted to ECCC a paper with Youming Qiao that gives an $latex {n^{O(\log\log n)}}&fg=000000$-time algorithm for the special case of central-radical groups, that is groups whose center coincides with the maximum solvable normal subgroup. This extends work by Laszló Babai and others from SODA 2011 and ICALP 2012, and the paper likewise gives more cases that are polynomial-time solvable.

Later I worked on graph isomorphism using what I call the ``beacon set method.'' This yielded strong results about random graphs, and also results about special families of graphs. The result on random graphs, for example, allowed an adversary to modify $latex {o(n)}&fg=000000$ of the edges of the graph, and still the isomorphism could be done in polynomial time with high probability.

The paper was never published---a mistake that one should avoid; publish all of your results. The paper did prove that isomorphism could be done in $latex {n^{O(\log n)}}&fg=000000$ time for symmetric graphs. Warning the first page of this paper comes up mostly blank, so scroll down to see the paper.

I---Ken writing some of these snippets from papers too---have remained relatively free of the isomorphism bug, except for formulating an open question about classifying ``which `graph-unravelings' are $latex {\mathsf{NP}}&fg=000000$-hard?'' in an earlier post. Still, I agree with Dick about a nice quote in the SODA 2014 paper on order types:

Isomorphism is probably one of the most fundamental problems for any discrete structure.

So we consider the SODA 2014 topics in turn.

Isomorphism For Lattices

The objects are lattices. Wait that word is used a lot in math. It could stand for according to this:

• Lattice (order), a partially ordered set with unique least upper bounds and greatest lower bounds.
• Lattice (group), a repeating arrangement of points.
• Lattice (discrete subgroup), a discrete subgroup of a topological group with finite co-volume.
• Lattice (module), a module over a ring embedded in a vector space over a field.
• Lattice graph, a graph that can be drawn within a repeating arrangement of points.
• Lattice multiplication, a multiplication algorithm suitable for hand calculation.
• Lattice model (finance), a method for evaluating stock options that divides time into discrete intervals.

The meaning used here is: a discrete subgroup which spans a real vector space. Every lattice, in this sense, has a basis and is formed by all integer linear combinations.

\includegraphics[width=3.5in]{lattice2.png}

Haviv and Regev study the natural question: when are two lattices isomorphic? Here this means that there is a rotation that moves one to the other. This sounds pretty simple, perhaps easy, but low-dimensional intuition often does not work in high dimensions. They prove:

Theorem 1 Isomorphism of lattices can be determined in time $latex {n^{O(n)}}&fg=000000$.

They actually prove much more: they find all the possible isomorphic mappings. A very neat result.

Their algorithm ``violates'' a informal rule that I, Dick, have found to be quite useful. The rule is: There are no natural decision algorithms whose running time is polynomial in $latex {n!}&fg=000000$. Of course an algorithm that list all the even permutations on $latex {n}&fg=000000$ letters must run in this type of time---there are that many outputs. But I have usually found that algorithms that run in a factorial type running time can be improved to run in exponential time $latex {2^{cn}}&fg=000000$.

Isomorphism For Order Types

The objects are sets of $latex {n}&fg=000000$ points in Euclidean $latex {d}&fg=000000$-dimensional space. The order type of a set of points is determined by the spatial structure of the points: it is not based on the exact distances of the points from each other. In the plane the order type of $latex {a,b,c}&fg=000000$ can be (i) clockwise, (ii) counter-clockwise, or (iii) collinear. The determinant of the matrix

$latex \displaystyle \begin{matrix}{ccc} a_{x} & a_{y} & 1 \\ b_{x} & b_{y} & 1 \\ c_{x} & c_{y} & 1 \end{matrix} &fg=000000$

Not surprisingly this all generalizes to any dimension. Two sets of $latex {n}&fg=000000$ points have the same order type provided there is a bijection between them that preserves the order.

The main result of Aloupis, Iacono, Langerman, \"Ozkan, and Wuhrer is:

Theorem 2 There is an algorithm that determines the order type of $latex {n}&fg=000000$ points in $latex {d}&fg=000000$-dimensional Euclidean space in time $latex {n^{O(d)}}&fg=000000$.

One notable feature of this result is that the points need not be in general position---there is no restriction on they arrangement. This seems like an important feature and should make the result have many more potential applications. An obvious question that occurs to us is: If there is an algorithm for testing isomorphism of order types for general position in time $latex {T}&fg=000000$ does that imply anything about un-restriction points? Can the general case be done in $latex {O(T)}&fg=000000$?

We note also that there is an answer to the question: How do five people get together to work on one problem? They started their work together at the 2011 Mid-Winter Workshop on Computational Geometry. So that is how we get papers with many authors. A great argument for more such workshops and meetings.

Isomorphism For Noisy Cases

We can also consider various approximative notions for graph isomorphism. One aspect of this comes from an old paper I wrote in 1999 with Anna Gál, Shai Halevi, and Erez Petrank, titled ``Computing From Partial Solutions.'' We showed that computing a partial isomorphism---that is getting just $latex {\log(n)}&fg=000000$-many entries pairs correct that extend to some isomorphism $latex {\phi}&fg=000000$ between two graphs $latex {G}&fg=000000$ and $latex {H}&fg=000000$---is as hard as GI itself. This also represented only a partial solution to the five-author question, since we stopped at four. However, we were soon out-done by a three-author solution: André Gro\ss{e}, Jörg Rothe, and Gerd Wechsung showed that getting even one pair $latex {\phi(u) = v}&fg=000000$ correct is as hard as computing some $latex {\phi}&fg=000000$.

The SODA 2014 paper by O'Donnell, Wright, Wu, and Zhou is emceed by Konstantin Makarychev in this CMU video, Zhou presenting. That doesn't quite make five people. Well the paper leans on a hypothesis by Uriel Feige that any polynomial-time randomized algorithm giving one-sided error on random $latex {\mathsf{3XOR}\text{-}\mathsf{SAT}}&fg=000000$ instances---that is with clauses of the form $latex {(x_i \oplus x_j \oplus x_k)}&fg=000000$ (possibly negated). Feige's hypothesis is that if such an algorithm never says ``no'' on an instance for which a $latex {(1-\epsilon)}&fg=000000$ portion of clauses can be satisfied, then it will incorrectly say ``yes'' on a large fraction of instances, those for which a portion almost $latex {1/8}&fg=000000$ cannot be satisfied; this is related to the Unique Games conjecture. So it almost has a fifth author.

Given two graphs $latex {G}&fg=000000$ and $latex {H}&fg=000000$ with the same numbers $latex {n}&fg=000000$ of vertices and $latex {m}&fg=000000$ of edges, call them ``almost isomorphic'' if for suitable $latex {\epsilon > 0}&fg=000000$ there is a bijection $latex {\phi: V(G) \longrightarrow V(H)}&fg=000000$ such that for all but $latex {\epsilon m}&fg=000000$ edges $latex {(u,v)}&fg=000000$ of $latex {G}&fg=000000$, $latex {(\phi(u),\phi(v))}&fg=000000$ is an edge of $latex {H}&fg=000000$. For suitable functions $latex {r}&fg=000000$ such that $latex {r(\epsilon) \longrightarrow 0}&fg=000000$ as $latex {\epsilon \longrightarrow 0}&fg=000000$, they define the ``Robust GI Problem'' as: Given two graphs that are $latex {\epsilon}&fg=000000$-almost isomorphic, compute a $latex {\phi'}&fg=000000$ that preserves a $latex {1 - r(\epsilon)}&fg=000000$ portion of edges.

They show that assuming Feige's hypothesis, there really is no polynomial-time algorithm for this problem. Or put another way, finding a polynomial-time algorithm for this problem suffices to falsify Feige's hypothesis. This is surprising insofar as GI is not $latex {\mathsf{NP}}&fg=000000$-complete unless the polynomial hierarchy collapses, while Feige's hypothesis involves a real form of $latex {\mathsf{SAT}}&fg=000000$. They also show unconditionally that a particular general family of polynomial-time algorithms based on semi-definite programming fails on this problem.

Open Problems

Are there more good cases of isomorphism to study? Are there even more relationships to Unique Games? Will SODA 2015 have more than three papers on this topic?