On the Complexity of Identifying Strongly Regular Graphs

Michael Levet ¹¹1 This work was partially supported by J. A. Grochow’s startup funds and NSF award CISE-2047756. I wish to thank C.J. Colbourn for helping me to find a copy of [Col79]. I also wish to thank J.N. Cooper and J.A. Grochow for helpful discussions. Department of Computer Science- University of Colorado Boulder

Abstract

In this paper, we show that Graph Isomorphism (GI) is not $\textsf{AC}^{0}$ -reducible to several problems, including the Latin Square Isotopy problem, isomorphism testing of several families of Steiner designs, and isomorphism testing of conference graphs. As a corollary, we obtain that GI is not $\textsf{AC}^{0}$ -reducible to isomorphism testing of Latin square graphs and strongly regular graphs arising from special cases of Steiner $2$ -designs. We accomplish this by showing that the generator-enumeration technique for each of these problems can be implemented in $\beta_{2}\textsf{FOLL}$ , which cannot compute Parity (Chattopadhyay, Torán, & Wagner, ACM Trans. Comp. Theory, 2013).

Keywords: Latin squares, Quasigroups, Graph Isomorphism, Steiner designs, Conference graphs.

1 Introduction

In one of the original papers on Graph Isomorphism (GI), by Corneil & Gotlieb, the authors observed that in practice, strongly regular graphs serve as difficult instances [CG70]. A common approach for producing such instances is to construct strongly regular graphs from combinatorial objects, such as Latin squares, nets (partial geometries), and combinatorial designs [CG70, SD76]. While strongly-regular graphs have been perceived as hard instances, there is little evidence to suggest that they are GI-complete.

There is a beautiful classification of strongly-regular graphs (of valency $\rho<n/2$ , which is essentially without loss of generality by taking complements) due to Neumaier [Neu79]. In using this classification in isomorphism testing, Spielman [Spi96] and Babai–Wilmes [BW13] organize it as follows:

(a)

Latin square graphs,
(b)

Line graphs of Steiner $2$ -designs satisfying $\rho<f(n)$ , for a certain function $f(n)\sim n^{3/4}$ ,
(c)

Strongly-regular graphs of degree $\rho=(n-1)/2$ (a.k.a. conference graphs),
(d)

Graphs satisfying a certain eigenvalue inequality referred to as Neumaier’s claw bound.

In this paper, we show (in particular) that (a) Latin square graphs, (b) line graphs arising from special cases of Steiner $2$ -designs, and (c) conference graphs are not GI-hard under $\textsf{AC}^{0}$ -computable many-one reductions. As with [CTW13], we show this by improving the parallel complexity of isomorphism testing in these classes of graphs to $\beta_{2}\textsf{FOLL}$ , which does not compute Parity (in the case of conference graphs, we achieve a stronger bound of $\beta_{2}\textsf{AC}^{0}$ ). As Parity is $\textsf{AC}^{0}$ -reducible to GI [Tor04], this rules out $\textsf{AC}^{0}$ -reductions (and more strongly, for any $i,c\geq 0$ , we rule out $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reductions).

Prior to our work, there were few pieces of complexity-theoretic evidence to suggest that strongly-regular graphs are not GI-complete. Babai showed that there is no functorial reduction from GI to the isomorphism testing of strongly-regular graphs [Bab14]. We note that almost all known reductions between isomorphism problems are functorial (c.f. [Bab14]). An example where this is not the case is the reduction from $1$ -Block Conjugacy of shifts of finite type to $k$ -Block Conjugacy [SF21, Theorem 18]. In the case of Quasigroup Isomorphism, Chattopadhyay, Torán, and Wagner improved the upper bound to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . In particular, they showed that for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to Quasigroup Isomorphism [CTW13].

Let us briefly discuss why problems such as Quasigroup Isomorphism, Latin Square Isotopy, and isomorphism testing of Steiner $2$ -designs are important from a complexity-theoretic perspective. Several families of strongly regular graphs (e.g., Latin square graphs, and the block-intersection graphs of Steiner $2$ -designs) arise naturally from the isomorphism problems from the underlying combinatorial objects. Precisely, many of these problems, including Quasigroup Isomorphism, Latin Square Isotopy, and isomorphism testing of Steiner $2$ -designs, are polynomial-time (and in fact, $\textsf{AC}^{0}$ ) reducible to GI. Polynomial-time solutions for these problems have been elusive. In particular, each of these problems are candidate NP-intermediate problems; that is, problems that belong to NP, but are neither in P nor NP-complete [Lad75].

There is considerable evidence suggesting that GI is not NP-complete [Sch88, BH92, IPZ01, Bab16, KST92, AK06, Mat79]. As Quasigroup Isomorphism, Latin Square Isotopy, and isomorphism testing of Steiner $2$ -designs reduce to GI, this evidence also suggests that none of these problems is NP-complete. Furthermore, Chattopadhyay, Torán, & Wagner [CTW13] showed that Quasigroup Isomorphism is not NP-complete under $\textsf{AC}^{0}$ -reductions, and our result shows the same for Latin Square Isotopy. In light of Babai’s $n^{\Theta(\log^{2}(n))}$ -time algorithm [Bab16], these problems serve as key barries to placing GI into P.

Main Results. In this paper, we show that several families of isomorphism problems characterized by the generator enumeration technique are not GI-complete under $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reductions, for any choice of $i,c\geq 0$ . In particular, this rules out $\textsf{AC}^{0}$ -reductions from GI to these problems. We also show that these results extend to the corresponding families of strongly regular graphs, providing complexity-theoretic evidence that isomorphism testing of strongly regular graphs may not be GI-complete.

The first problem we consider is the Latin Square Isotopy problem, which takes as input two quasigroups $L_{1},L_{2}$ given by their multiplication tables and asks if there exist bijections $\alpha,\beta,\gamma:L_{1}\to L_{2}$ such that $\alpha(x)\beta(y)=\gamma(xy)$ for all $x,y\in L_{1}$ .

Theorem 1.1.

$\textsc{Latin Square Isotopy}\in\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

Remark 1.2.

This improves the previous bound of $\beta_{2}\textsf{NC}^{2}$ due to Wolf [Wol94].

To prove Theorem 1.1, we leverage cube generating sequences, in a similar manner as Chattopadhyay, Torán, & Wagner [CTW13, Theorem 3.4]. After non-deterministically guessing cube generating sequences, we can check in $\textsf{L}\cap\textsf{FOLL}$ whether the induced map extends to an isotopy of the Latin squares.

Now for any $i,c\geq 0$ , we have that $\beta_{i}\textsf{FO}((\log\log n)^{c})$ cannot compute Parity [CTW13]. Thus, we obtain the following corollary.

Corollary 1.3.

For any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to Latin Square Isotopy.

Latin squares yield a corresponding family of strongly regular graphs, known as Latin square graphs, where two Latin square graphs $G_{1}$ and $G_{2}$ are isomorphic if and only if their corresponding Latin squares $L(G_{1})$ and $L(G_{2})$ are main class isotopic [Mil78, Lemma 3] (that is, the Latin squares can be put into compatible normal forms that correspond to isomorphic quasigroups). Miller previously showed that it is possible to recover the corresponding Latin square from a Latin square graph in polynomial-time [Mil78], and Wolf strengthened the analysis to show that this reduction is in fact $\textsf{NC}^{1}$ -computable [Wol94]. A closer analysis yields that this reduction is actually $\textsf{AC}^{0}$ -computable (see Lemma 3.9). Furthermore, we can place a Latin square into its main isotopy class in $\textsf{AC}^{0}$ (see Remark 1.6). Thus, we obtain the following corollary.

Corollary 1.4.

Deciding whether two Latin square graphs are isomorphic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . Consequently, for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of Latin square graphs.

Remark 1.5.

It is also possible to construct a Latin square graph from a Latin square using an $\textsf{AC}^{0}$ -circuit. Thus, Latin Square Isotopy and isomorphism-testing of Latin square graphs are equivalent under $\textsf{AC}^{0}$ -reductions.

Remark 1.6.

We sketch an alternative proof of Theorem 1.1 and Corollary 1.4. In Miller’s [Mil78] first proof that Latin Square Isotopy is solvable in time $n^{\log(n)+O(1)}$ , Miller takes one Latin square $L^{\prime}$ and places it in a normal form. Miller shows that this step is polynomial-time computable. A closer analysis shows that it is in fact $\textsf{AC}^{0}$ -computable: we may label the first row and first column as $1,2,\ldots,n$ . We then in $\textsf{AC}^{0}$ fill in the remaining cells of the normal form. For the second Latin square $L$ , Miller places $L$ in $n^{2}$ possible normal forms by guessing the element to label as $1$ . We may consider all such guesses in parallel, and so this step is also $\textsf{AC}^{0}$ -computable. Miller then checks whether the normal form of $L^{\prime}$ and the normal form of $L$ are isomorphic as quasigroups. This step is $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ -computable [CTW13]. Thus, we have an $\textsf{AC}^{0}$ -computable disjunctive truth-table reduction (see Section 2.2) from Latin Square Isotopy to Quasigroup Isomorphism, which places Latin Square Isotopy into $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . We note that Wolf’s [Wol94] proof that $\textsc{Latin Square Isotopy}\in\beta_{2}\textsf{NC}^{2}$ followed a similar strategy as Miller’s [Mil78] proof that Quasigroup Isomorphism can be solved in time $n^{\log(n)+O(1)}$ .

As we can recover a Latin square from a Latin square graph in $\textsf{AC}^{0}$ (see Lemma 3.9), we also have an $\textsf{AC}^{0}$ -computable disjunctive truth table reduction from isomorphism testing of Latin square graphs to Quasigroup Isomorphism. So isomorphism testing of Latin square graphs belongs to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

Instead, the proof we give of Theorem 1.1 (see Section 3) exhibits how the technique of cube generating sequences [CTW13] can be fruitfully applied directly to isotopy (rather than isomorphism) of algebraic structures, which we do by combining cube generating sequences with Miller’s [Mil78] second proof that Latin Square Isotopy can be solved in time $n^{\log(n)+O(1)}$ .

We now turn our attention to isomorphism testing of Steiner designs.

Theorem 1.7.

For any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of Steiner $(t,t+1)$ -designs.

We prove Theorem 1.7 in two steps. First, we establish the case of $t=2$ , which is the case of Steiner triple systems. It is well-known that Steiner triple systems correspond to quasigroups, and that this reduction is polynomial-time computable [Mil78]. A careful analysis shows that this reduction is in fact $\textsf{AC}^{0}$ -computable. Furthermore, we observe that the reduction in [BW13, Theorem 33] from isomorphism testing of Steiner $t$ -designs to isomorphism testing of Steiner $2$ -designs is $\beta_{2}\textsf{AC}^{0}$ -computable. As a corollary, isomorphism testing of Steiner $(t,t+1)$ -designs is $\beta_{2}\textsf{AC}^{0}$ -reducible to isomorphism testing of Steiner triple systems, and hence Quasigroup Isomorphism.

Steiner designs yield a family of graphs known as block intersection graphs. In the case of Steiner $2$ -designs, these graphs are strongly regular. When the block size is bounded, we observe that we may recover a Steiner $2$ -design from its block-incidence graph in $\textsf{AC}^{0}$ . If the block size is not bounded, this reduction is $\textsf{TC}^{0}$ -computable. In the case of Steiner triple systems, this yields the following corollary.

Corollary 1.8.

Let $G_{1},G_{2}$ be block-incidence graphs arising from Steiner triple systems. We can decide whether $G_{1}\cong G_{2}$ in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . Consequently, for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of block-incidence graphs arising from Steiner triple systems.

We finally consider the case of conference graphs.

Theorem 1.9.

Isomorphism testing between a conference graph $G$ and an arbitrary graph $H$ belongs to $\beta_{2}\textsf{AC}^{0}$ . Consequently, for any $i,c\geq 0$ , there is no $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reduction from GI to isomorphism testing of conference graphs.

To prove Theorem 1.9, we use a result of Babai [Bab80], who showed that conference graphs admit so called distinguishing sets (see Section 5) of size $O(\log n)$ . Distinguishing sets are quite powerful: after indvidiualizing the vertices in a distinguishing set, only two rounds of the count-free Color Refinement algorithm are needed to assign each vertex in the graph a unique label. The $\beta_{2}\textsf{AC}^{0}$ algorithm thus works as follows: we first guess such a set $S$ using $O(\log^{2}n)$ non-deterministic bits, individualize the vertices in $S$ , and then run two rounds of the count-free Color Refinement algorithm.

Remark 1.10.

Theorem 1.9 provides evidence that isomorphism testing of conference graphs might in fact be easier than Group Isomorphism (and hence, isomorphism testing of Latin square graphs and Steiner designs). The best known complexity-theoretic upper bound for Group Isomorphism is $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}\cap\beta_{2}\textsf{SC}^{2}$ (the $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ is due to Chattopadhyay, Torán, & Wagner [CTW13]; Tang [Tan13] established the $\beta_{2}\textsf{SC}^{2}$ bound and provided an alternative proof of the $\beta_{2}\textsf{L}$ bound). Even after fixing a cube generating sequence, it is not clear that an AC circuit of depth $o(\log\log n)$ and polynomial size could uniquely identify each group element.

These differences are quite opaque when examined from the algorithmic perspective. Both conference graphs and groups admit $n^{\Theta(\log n)}$ -time isomorphism tests that have seen little improvement in the worst case in over 40 years. For conference graphs, this bound is achieved using Babai’s [Bab80] result showing the existence of size $O(\log n)$ distinguishing sets. In the setting of groups, Tarjan (c.f., [Mil78]) leveraged the fact that every group admits a generating set of size $\leq\lceil\log_{p}n\rceil$ (where $p$ is the smallest prime dividing $n$ ) to obtain an $n^{\log_{p}(n)+O(1)}$ isomorphism test via the generator enumeration strategy. Rosenbaum [Ros13] (see [LGR16, Sec. 2.2]) improved this to $n^{(1/4)\log_{p}(n)+O(1)}$ . And even the impressive body of work on practical algorithms for this problem, led by Eick, Holt, Leedham-Green and O’Brien (e. g., [BEO02, ELGO02, BE99, CH03]) still results in an $n^{\Theta(\log n)}$ -time²²2Where we stress $n=|G|$ . In the setting of practical algorithms, the groups are often given by generating sequences, and so polynomial time in the size of the succinct input is $\operatorname{poly}\log|G|$ . algorithm in the general case (see [Wil19, Page 2]).

Further Related Work. There has been significant work on isomorphism testing of strongly regular graphs. In 1980, Babai used a simple combinatorial approach to test strongly regular graphs on $n$ vertices and degree $\rho<n/2$ in time $\text{exp}(O((n/\rho)\log^{2}n))$ [Bab80, Bab81]. We note that the complement of a strongly-regular graph is strongly regular, hence the assumptions on the degree. As $\rho\geq\sqrt{n-1}$ , this gives an algorithm in moderately exponential time $\text{exp}(O(\sqrt{n}\log^{2}n))$ for all $\rho$ . Spielman [Spi96] subsequently improved this $\text{exp}(O((n/\rho)\log^{2}n))$ bound to $\exp(O(n^{1/3}\log^{2}n))$ . This improved upon what was at the time, the best known bound of $\exp(O(\sqrt{n\log n}))$ for isomorphism testing of general graphs [BL83, BKL83, ZKT85] based on Luks’ group theoretic method [Luk82].

We note that Babai’s [Bab80] work already handled the case of conference graphs in time $n^{O(\log n)}$ . Furthermore, the works of Babai and Spielman sufficed to handle isomorphism testing of strongly regular graphs that satisfy Neumaier’s claw bound. Namely, Spielman [Spi96] handled the case of $\rho\in o(n^{2/3})$ in time $\text{exp}(O(n^{1/4}\log^{2}n))$ , and Babai [Bab80] handled the case of $\rho\in\Omega(n^{2/3})$ in time $\text{exp}(O(n^{1/3}\log^{2}n))$ .

In the case of Latin square graphs, Miller [Mil78] resolved this in time $n^{O(\log n)}$ . Wolf improved the complexity theoretic bound to $\beta_{2}\textsf{NC}^{2}$ (uniform $\textsf{NC}^{2}$ -circuits that accept $O(\log^{2}n)$ existentially quantified non-deterministic bits).

The isomorphism problem for Steiner $2$ -designs also dates back to Miller [Mil78], who considered the special cases of Steiner triple systems (Steiner $(2,3,n)$ -designs), projective planes (Steiner $(2,q+1,q^{2}+q+1)$ -designs), and affine planes (Steiner $(2,q,q^{2})$ -designs). In the case of Steiner triple systems, Miller leveraged a standard reduction to Quasigroup Isomorphism to obtain an $n^{O(\log n)}$ upper bound. M. Colbourn [Col79] subsequently extended this result to obtain an $v^{O(\log v)}$ canonization procedure for Steiner $(t,t+1)$ -designs.

For the cases of projective and affine planes, Miller [Mil78] showed that isomorphism testing can be done in time $n^{O(\log\log n)}$ . In particular, Miller showed that the corresponding structures may be recovered from the block-intersection graphs in polynomial-time, providing the block-intersection graphs are of sufficiently high degree [Mil78]. Thus, isomorphism testing of block-intersection graphs arising from Steiner triple systems can be done in time $n^{O(\log n)}$ , and the block-intersection graphs arising from projective and affine planes can be identified in time $n^{O(\log\log n)}$ .

In 1983, Babai & Luks showed that Steiner $2$ -designs with blocks of bounded size admit an $n^{O(\log n)}$ canonization procedure (and hence, isomorphism test). In paritcular, isomorphism testing of the corresponding block-intersection graphs is solvable in time $n^{O(\log n)}$ [BL83]. Here, Babai & Luks utilized Luks’ group theoretic method [Luk82]. Huber later extended this result to obtain an $n^{O(\log n)}$ -runtime isomorphism test for arbitrary $t$ -designs, where both $t$ and the block size are bounded, as well as the corresponding block-intersection graphs [Hub11].

Spielman solved the general case of strongly-regular graphs of degree $f(n)\sim n^{3/4}$ arising from Steiner $2$ -designs in time $\text{exp}(O(n^{1/4}\log^{2}n))$ [Spi96]. Independently, Babai & Wilmes [BW13] and Chen, Sun, & Teng [CST13] exhibited an $n^{O(\log n)}$ -runtime isomorphism test for both Steiner $2$ -designs and the corresponding block-intersection graphs. Babai & Wilmes extended their result to Steiner $t$ -designs. Here, each of these papers utilized the individualize and refine technique [Spi96, BW13, CST13].

The isomorphism problem for combinatorial designs is another candidate NP-intermediate problem. In the general case, testing whether two combinatorial designs are isomorphic is GI-complete under polynomial-time Turing reductions [CC81]. Cyclic Steiner $2$ -designs of prime order are known to admit a polynomial-time isomorphism test [CM80]. To the best of our knowledge, the complexity of deciding whether two cyclic Steiner $2$ -designs are isomorphic remains open for arbitrary orders.

2 Preliminaries

2.1 Algebra and Combinatorics

Graph Theory. A strongly regular graph with parameters $(n,k,\lambda,\mu)$ is a simple, undirected $k$ -regular, $n$ -vertex graph $G(V,E)$ where any two adjacent vertices share $\lambda$ neighbors, and any two non-adjacent vertices share $\mu$ neighbors. The complement of a strongly regular graph is also strongly regular, with parameters $(n,n-k-1,n-2-2k+\mu,n-2k+\lambda)$ .

Quasigroups. A quasigroup consists of a set $G$ and a binary operation $\star:G\times G\to G$ satisfying the following. For every $a,b\in G$ , there exist unique $x,y$ such that $a\star x=b$ and $y\star a=b$ . When the multiplication operation is understood, we simply write $ax$ for $a\star x$ .

Unless otherwise stated, all quasigroups are assumed to be finite and represented using their Cayley (multiplication) tables. For a quasigroup of order $n$ , thet Cayley table has $n^{2}$ entries, each represented by a string of size $\lceil\log_{2}(n)\rceil$ .

A Latin square of order $n$ is an $n\times n$ matrix $L$ where each cell $L_{ij}\in[n]$ , and each element of $[n]$ appears exactly once in a given row or a given column. Latin squares are precisely the Cayley tables corresponding to quasigroups. We will abuse notation by referring to a quasigroup and its multiplication table interchangeably. An isotopy of Latin squares $L_{1}$ and $L_{2}$ is an ordered triple $(\alpha,\beta,\gamma)$ , where $\alpha,\beta,\gamma:L_{1}\to L_{2}$ are bijections satisfying the following: whenever $ab=c$ in $L_{1}$ , we have that $\alpha(a)\beta(b)=\gamma(c)$ in $L_{2}$ . Alternatively, we may view $\alpha$ as a permutation of the rows of $L_{1}$ , $\beta$ as a permutation of the rows of $L_{2}$ , and $\gamma$ as a permutation of the values in the table. Here, $L_{1}$ and $L_{2}$ are isotopic precisely if (i) the $(i,j)$ entry of $L_{1}$ is the $(\alpha(i),\beta(j))$ entry of $L_{2}$ , and (ii) $x$ is the $(i,j)$ entry of $L_{1}$ if and only if $\gamma(x)$ is the $(\alpha(i),\beta(j))$ entry of $L_{2}$ .

As quasigroups are non-associative, the parenthesization of a given expression may impact the resulting value. We restrict attention to balanced parenthesizations, which ensure that words of the form $g_{0}g_{1}\cdots g_{k}$ are evaluated using a balanced binary tree with $k+1$ leves and therefore depth $O(\log\log n)$ .

For a sequence $S:=(s_{0},s_{1},\ldots,s_{k})$ from a quasigroup, define:

\text{Cube}(S)=\{s_{0}s_{1}^{e_{1}}\cdots s_{k}^{e_{k}}:e_{1},\ldots,e_{k}\in\{0,1\}\}.

We say that $S$ is a cube generating sequence if each element $g$ in the quasigroup can be written as $g=s_{0}s_{1}^{e_{1}}\cdots s_{k}^{e_{k}}$ , for $e_{1},\ldots,e_{k}\in\{0,1\}$ . Every quasigroup is known to admit a cube generating sequence of size $O(\log n)$ [CTW13].

For a given Latin square $L$ of order $n$ , we associate a Latin square graph $G(L)$ that has $n^{2}$ vertices; one for each triple $(a,b,c)$ that satisfies $ab=c$ . Two vertices $(a,b,c)$ and $(x,y,z)$ are adjacent in $G(L)$ precisely if $a=x$ , $b=y$ , or $c=z$ . Miller showed that two Latin square graphs $G_{1}$ and $G_{2}$ are isomorphic if and only if the corresponding Latin squares, $L_{1}$ and $L_{2}$ , are main class isotopic; that is, if $L_{1}$ and $L_{2}$ can be placed into compatible normal forms that correspond to isomorphic quasigroups [Mil78]. A Latin square graph on $n^{2}$ vertices is a strongly regular graph with parameters $(n^{2},3(n-1),n,6)$ . Conversely, a strongly regular graph with these same parameters $(n^{2},3(n-1),n,6)$ is called a pseudo-Latin square graph. Bruck showed that for $n>23$ , a pseudo-Latin square graph is a Latin square graph [Bru63].

Albert showed that a quasigroup $Q$ is isotopic to a group $G$ if and only if $Q$ is isomorphic to $G$ . In general, isotopic quasigroups need not be isomorphic [Alb43].

Nets. A net or partial geometry of order $n\geq 1$ and degree $k\geq 1$ , denoted $\mathcal{N}(n,k)$ , consists of a set $P$ of $n^{2}$ points and a set $L$ of $kn$ lines satisfying the following.

(a)

Each line in $L$ has $n$ points.
(b)

Each point in $P$ lies on exactly $k$ distinct lines.
(c)

The $kn$ lines of $L$ fall into $k$ parallel classes. No two lines in the same parallel class intersect. If $\ell_{1},\ell_{2}\in L$ are in different parallel classes, then $\ell_{1}$ and $\ell_{2}$ share exactly one common point.

Necessarily, $k\leq n+1$ . If $k=n+1$ , then the net is called an affine plane of order $n$ . A projective plane is the extension of an affine plane $\mathcal{N}$ by adding $n+1$ new points $p_{1},\ldots,p_{n+1}$ (one per parallel class). The point $p_{i}$ is then added to each line of the $i$ th parallel class. We finally add a new line containing $\{p_{1},\ldots,p_{n+1}\}$ . We may recover an affine plane from a projective plane by removing a line and the associated points from the projective plane. We assume that nets are given by the point-block incidence matrix.

Given a net $\mathcal{N}(n,k)$ where $k\leq n$ , we may construct a net graph of order $n$ and degree $k$ $G(V,E)$ on $n^{2}$ vertices corresponding to the points in $\mathcal{N}$ . Two vertices are adjacent in $G$ if their corresponding points in $\mathcal{N}$ determine a line. We note that a net graph uniquely determines the net $\mathcal{N}(n,k)$ [Bru63]. Miller showed that, provided $n>(k-1)^{2}$ , this equivalence holds under polynomial-time reductions [Mil78]. A net graph is strongly-regular with parameters $(n^{2},k(n-1),n-2+(k-1)(k-2),k(k-1))$ . Conversely, a strongly regular graph with parameters $(n^{2},k(n-1),n-2+(k-1)(k-2),k(k-1))$ is referred to as a pseudo-net graph. Bruck showed that for $n$ sufficiently large, a pseudo-net graph of order $n$ and degree $k$ is a net graph [Bru63].

Designs. Let $t\leq k\leq v$ and $\lambda$ be positive integers. A $(t,k,\lambda,v)$ design is an incidence structure $\mathcal{D}=(X,\mathcal{B},I)$ , where $X$ denotes our set of $v$ points. Now $\mathcal{B}$ is a subset of $\binom{X}{k}$ , where each element of $\mathcal{B}$ is referred to as a block, satisfying the property that each $t$ -element subset of $X$ belongs to exactly $\lambda$ blocks. If $t<k<v$ , we say that the design is non-trivial. If $\lambda=1$ , the design is referred to as a Steiner design. We denote Steiner designs as $(t,k,v)$ -designs when we want to specify $v$ the number of points, or Steiner $(t,k)$ -designs when referring to a family of designs. We note that Steiner $(2,3)$ -designs are known as Steiner triple systems. Projective planes are Steiner $(2,q+1,q^{2}+q+1)$ -designs, and affine planes are Steiner $(2,q,q^{2})$ -designs. We assume that designs are given by the point-block incidence matrix.

Let $\mathcal{D}=(X,\mathcal{B},I)$ be a design, and let $A\subseteq X$ . The derived design at $A$ , denoted $\mathcal{D}(A)$ , has the set of points $X\setminus A$ and blocks $\{B\setminus A:B\in\mathcal{B},A\subsetneq B\}$ . If $\mathcal{D}$ is a Steiner $(t,k,v)$ -design, then $\mathcal{D}(A)$ is a Steiner $(t-|A|,k-|A|,v-|A|)$ -design.

For a design $\mathcal{D}=(X,\mathcal{B},I)$ , we may define a block intersection graph (also known as a line graph) $G(V,E)$ , where $V(G)=\mathcal{B}$ and two blocks $B_{1},B_{2}$ are adjacent in $G$ if and only if $B_{1}\cap B_{2}\neq\emptyset$ . In the case of a Steiner $2$ -design, the block-intersection graph is strongly regular. For Steiner triple systems, the block-intersection graphs are strongly regular with parameters $(n(n-1)/6,3(n-3)/2,(n+3)/2,9)$ . Conversely, strongly regular graphs with the parameters $(n(n-1)/6,3(n-3)/2,(n+3)/2,9)$ are referred to as pseudo-STS graphs. Bose showed that pseudo-STS graphs graphs with strictly more than $67$ vertices are in fact STS graphs [Bos63].

2.2 Computational Complexity

We assume familiarity with Turing machines and the complexity classes $\textsf{P},\textsf{NP},\textsf{L}$ , and NL- we refer the reader to standard references [Zoo, AB09].

Circuit Complexity. For a standard reference, see [Vol99]. We consider Boolean circuits using the AND, OR, NOT, and Majority, where $\textsf{Majority}(x_{1},\ldots,x_{n})=1$ if and only if $\geq n/2$ of the inputs are $1$ . Otherwise, $\textsf{Majority}(x_{1},\ldots,x_{n})=0$ . In this paper, we will consider logspace uniform circuit families $(C_{n})_{n\in\mathbb{N}}$ , in which a deterministic logspace Turing machine can compute the map $1^{n}\mapsto\langle C_{n}\rangle$ (here, $\langle C_{n}\rangle$ denotes an encoding of the circuit $C_{n}$ ).

Definition 2.1.

Fix $k\geq 0$ . We say that a language $L$ belongs to (logspace uniform) $\textsf{NC}^{k}$ if there exist a (logspace uniform) family of circuits $(C_{n})_{n\in\mathbb{N}}$ over the $\textsf{AND},\textsf{OR},\textsf{NOT}$ gates such that the following hold:

•

The AND and OR gates take exactly $2$ inputs. That is, they have fan-in $2$ .
•

$C_{n}$ has depth $O(\log^{k}n)$ and uses (has size) $n^{O(1)}$ gates. Here, the implicit constants in the circuit depth and size depend only on $L$ .
•

$x\in L$ if and only if $C_{|x|}(x)=1$ .

The complexity class $\textsf{AC}^{k}$ is defined analogously as $\textsf{NC}^{k}$ , except that the $\textsf{AND},\textsf{OR}$ gates are permitted to have unbounded fan-in. That is, a single AND gate can compute an arbitrary conjunction, and a single OR gate can compute an arbitrary disjunction. The complexity class $\textsf{TC}^{k}$ is defined analogously as $\textsf{AC}^{k}$ , except that our circuits are now permitted Majority gates of unbounded fan-in. For every $k$ , the following containments are well-known:

\textsf{NC}^{k}\subseteq\textsf{AC}^{k}\subseteq\textsf{TC}^{k}\subseteq\textsf{NC}^{k+1}.

In the case of $k=0$ , we have that:

\textsf{NC}^{0}\subsetneq\textsf{AC}^{0}\subsetneq\textsf{TC}^{0}\subseteq\textsf{NC}^{1}\subseteq\textsf{L}\subseteq\textsf{NL}\subseteq\textsf{AC}^{1}.

We note that functions that are $\textsf{NC}^{0}$ -computable can only depend on a bounded number of input bits. Thus, $\textsf{NC}^{0}$ is unable to compute the AND function. It is a classical result that $\textsf{AC}^{0}$ is unable to compute Parity [Smo87]. The containment $\textsf{TC}^{0}\subseteq\textsf{NC}^{1}$ (and hence, $\textsf{TC}^{k}\subseteq\textsf{NC}^{k+1}$ ) follows from the fact that $\textsf{NC}^{1}$ can simulate the Majority gate. The class NC is:

\textsf{NC}:=\bigcup_{k\in\mathbb{N}}\textsf{NC}^{k}=\bigcup_{k\in\mathbb{N}}\textsf{AC}^{k}=\bigcup_{k\in\mathbb{N}}\textsf{TC}^{k}.

It is known that $\textsf{NC}\subseteq\textsf{P}$ , and it is believed that this containment is strict.

Let $d:\mathbb{N}\to\mathbb{N}$ be a function. The complexity class $\textsf{FO}(d(n))$ is the set of languages decidable by uniform AC circuit families of depth $O(d(n))$ and polynomial size. The complexity class $\textsf{FOLL}=\textsf{FO}(\log\log n)$ . It is known that $\textsf{AC}^{0}\subsetneq\textsf{FOLL}\subsetneq\textsf{AC}^{1}$ , and it is open as to whether FOLL is contained in NL [BKLM01].

For a complexity class $\mathcal{C}$ , we define $\beta_{i}\mathcal{C}$ to be the set of languages $L$ such that there exists an $L^{\prime}\in\mathcal{C}$ such that $x\in L$ if and only if there exists $y$ of length at most $O(\log^{i}|x|)$ such that $(x,y)\in L^{\prime}$ . For any $i,c\geq 0$ , $\beta_{i}\textsf{FO}((\log\log n)^{c})$ cannot compute Parity [CTW13].

Reductions. We will consider several notions of reducibility. Let $L_{1},L_{2}$ be languages. We say that $L_{1}$ is many-one reducible to $L_{2}$ , denoted $L_{1}\leq_{m}L_{2}$ , if there exists a computable function $\varphi:\{0,1\}^{*}\to\{0,1\}^{*}$ such that $x\in L_{1}\iff\varphi(x)\in L_{2}$ . We will often ask that, for a given complexity $\mathcal{C}$ , $\varphi$ is $\mathcal{C}$ -computable.

We now turn towards recalling the notion of a Turing reduction. Intuitively, we say that the language $L_{1}$ is Turing-reducible to $L_{2}$ if, given an algorithm to solve $L_{2}$ , we can design an algorithm to solve $L_{1}$ . This is made precise with oracle Turing machines, which we recall now. An oracle Turing machine is a Turing machine with a separate oracle tape and oracle query state. When the Turing machine enters the query state, it transitions to one of two specified states based on whether the string on the oracle tape belongs to the oracle. When the oracle is unspecified, we write $M^{\square}$ . When the oracle $\mathcal{O}$ is specified, we write $M^{\mathcal{O}}$ . We now make precise the notion of a Turing reduction.

A Turing reduction from $L_{1}$ to $L_{2}$ is an oracle Turing machine $M^{\square}$ such that $M^{L_{2}}$ decides $L_{1}$ . If there exists a Turing reduction from $L_{1}$ to $L_{2}$ , we write $L_{1}\leq_{T}L_{2}$ . We will be particularly interested in Turing reductions from $L_{1}$ to $L_{2}$ , where $M^{L_{2}}$ runs in polynomial time.

We finally recall the notion of a truth-table reduction. Again let $L_{1},L_{2}$ be languages. We say that $L_{1}$ is truth-table reducible to $L_{2}$ , denoted $L_{1}\leq_{tt}L_{2}$ , if there exists a computable function $g$ mapping an input $X$ to inputs $Y_{1},\ldots,Y_{k}$ , and a computable function $f$ (called the truth-table predicate), which depends on $X$ and maps $\{0,1\}^{k}\to\{0,1\}$ such that $X\in L_{1}$ if and only if $f(\chi_{L_{2}}(Y_{1}),\ldots,\chi_{L_{2}}(Y_{k}))=1$ (where $\chi_{L_{2}}$ is the characteristic function for $L_{2}$ ). The truth-table reduction is disjunctive if $f$ is the OR function. We say that the truth-table reduction is $\mathcal{C}$ -computable if both $f,g$ are $\mathcal{C}$ -computable.

It is known that:

L_{1}\leq_{m}L_{2}\implies L_{1}\leq_{tt}L_{2}\implies L_{1}\leq_{T}L_{2},

and that this chain of implications holds even in the presence of resource constraints (e.g., if we were to insist that all steps be P-computable). Some care has to be taken to formulate a precise notion of a Turing reduction for circuit classes. Fortunately, we will not need the notion of a Turing reduction for circuit classes, and so we will not discuss this further.

Graph Isomorphism. We refer to GI as the decision problem Graph Isomorphism, which takes as input two graphs and asks whether there is an isomorphism between them. The complexity class GI is the set of decision problems that are polynomial-time Turing reducible to GI.

2.3 Color Refinement

Let $G$ be a graph. The Color Refinement (or $1$ -dimensional Weisfeiler–Leman) algorithm works by iteratively coloring the vertices of $G$ in an isomorphism invariant manner. The algorithm begins by assigning each vertex an initial color based on their degree; that is, $\chi_{0}(v)=\text{deg}(v)$ . Now for $r\geq 0$ , we refine the coloring in the following manner:

\chi_{r+1}(u)=(\chi_{r}(u),\{\!\{\chi_{r}(v):v\in N(u)\}\!\}),

where $\{\!\{\cdot\}\!\}$ denotes a multiset. The count-free variant of Color Refinement works analogously, except the refinement step considers the set rather than multiset of colors at each round:

\chi_{r+1}(u)=(\chi_{r}(u),\{\chi_{r}(v):v\in N(u)\}).

The algorithm terminates when the partition on the vertices induced by the coloring is not refined. We can use Color Refinement can as a non-isomorphism test by running the algorithm on $G\dot{\cup}H$ and comparing the multiset of colors. Note that if at round $r$ , if the multiset of colors for $G$ differs from $H$ , then we can conclude that $G\not\cong H$ . Each iteration of the standard counting Color Refinement can be implemented using a logspace uniform $\textsf{TC}^{0}$ -circuit, and each iteration of the count-free Color Refinement can be implemented using a logspace uniform $\textsf{AC}^{0}$ -circuit (c.f., the work of Grohe & Verbitsky [GV06] who observed this for $k$ -dimensional Weisfeiler–Leman where $k\geq 2$ . The analogous parallel implementation holds for Color Refinement).

The individualize-and-refine paradigm works as follows. Let $S$ be a sequence of vertices in $G$ . We first assign each vertex in $S$ a unique color (so no two vertices in $S$ have the same color, and no vertex in $V(G)-S$ has the same color as any vertex in $S$ ), and then run Weisfeiler–Leman. The refinement step is usually performed using Color Refinement ( $1$ -WL), but may be performed using higher-dimensional Weisfeiler–Leman. For the purposes of this paper, we will use the count-free variant of Color Refinement in the refinement step.

It is known that even higher-dimensional Weisfeiler–Leman fails to place GI into P [CFI92, NS18]. We refer to Sandra Kiefer’s dissertation [Kie19] for a thorough and current survey of Weisfeiler–Leman.

3 Latin Square Isotopy

In this section, we show that the Latin Square Isotopy problem is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . The key technique is to guess cube generating sequences $A$ and $B$ for the Latin square $L_{1}$ , and cube generating sequences $A^{\prime},B^{\prime}$ for the Latin square $L_{2}$ . We then (attempt to) construct appropriate bijections $\alpha,\beta:L_{1}\to L_{2}$ , where $\alpha$ extends the map from $A\to A^{\prime}$ and $\beta$ extends the map from $B\to B^{\prime}$ . We can construct such bijections in $\textsf{FOLL}\cap\textsf{L}$ using the techniques from Chattopadhyay, Torán, and Wagner [CTW13].

The key step remains in checking whether the map sending the product of each pair $(x,y)\in L_{1}\times L_{1}$ , $xy\mapsto\alpha(x)\beta(y)$ a bijection. Wolf approaches this in the following manner. First, construct sets $C=\{a_{i}b_{i}:a_{i}\in A,b_{i}\in B\}$ and $C^{\prime}=\{a_{i}^{\prime}b_{i}^{\prime}:a_{i}^{\prime}\in A^{\prime},b_{i}^{\prime}\in B^{\prime}\}$ . Then check whether the map $a_{i}b_{i}\mapsto a_{i}^{\prime}b_{i}^{\prime}$ extends to a bijection $\gamma:L_{1}\to L_{2}$ . Finally, check whether $\alpha(x)\beta(y)=\gamma(xy)$ for all $x,y\in L_{1}$ . We note that Wolf is able to do this in $\textsf{NC}^{2}$ [Wol94]. If $C$ and $C^{\prime}$ are cube generating sequences, then we would be able to apply the technique of Chattophadyay, Torán, and Wagner [CTW13] to compute the bijection $\gamma$ in $\textsf{FOLL}\cap\textsf{L}$ . However, $C$ and $C^{\prime}$ need not be cube generating sequences. As an example in the case of groups, suppose that $B=A^{-1}$ . Then $B$ is a cube generating sequence. Furthermore, $a_{i}b_{i}=1$ for each $i$ , and so $C$ has only the identity element. In general, we do not expect $C$ and $C^{\prime}$ to be cube generating sequences, even if they do generate $L_{1}$ and $L_{2}$ respectively.

Instead of extending Wolf’s technique, we extend Miller’s technique in his second proof that
Latin Square Isotopy is decidable in time $n^{\log(n)+O(1)}$ . Miller constructs the relation

R=\{(xy,\alpha(x)\beta(y)):x,y\in L_{1}\},

and checks whether $R$ is a bijection. If $R$ is a bijection; then by construction, the triple $(\alpha,\beta,R)$ is an isotopy [Mil78, Theorem 2, Proof 2]. Using the fact that $A$ and $B$ are cube generating sequences, we can compute $x$ and $y$ in $\textsf{L}\cap\textsf{FOLL}$ . In the process of computing $\alpha$ and $\beta$ , we obtain a data structure which allows us to compute $\alpha(x)$ and $\beta(y)$ in $\textsf{L}\cap\textsf{FOLL}$ .

Theorem 3.1.

Latin Square Isotopy is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

We begin with the following lemmas.

Lemma 3.2.

Let $A,B$ be finite sets of the same size, and let $R\subseteq A\times B$ be a relation. We can decide whether $R$ is a well-defined surjection (and as $|A|=|B|$ , consequently whether $R$ is a well-defined bijection) in $\textsf{AC}^{0}$ .

Proof.

For each $b\in B$ , define the relation:

Y(b)=\bigvee_{a\in A}1_{(a,b)\in R}.

Observe that $Y(b)$ is $\textsf{AC}^{0}$ -computable. Now $R$ is surjective if and only if $Y(b)=1$ for all $b\in B$ , which is defined by the following condition:

\varphi:=\bigwedge_{b\in B}Y(b).

Observe that $\varphi$ is $\textsf{AC}^{0}$ computable. ∎

Lemma 3.3.

Let $L_{1}$ and $L_{2}$ be Latin squares of order $n$ , and let $k=4\lceil\log(n)\rceil$ . Suppose that $(g_{0},g_{1},\ldots,g_{k})$ and $(h_{0},\ldots,h_{k})$ are cube generating sequences for $L_{1}$ and $L_{2}$ respectively, with balanced parenthesization $P$ . Deciding whether the map $g_{i}\mapsto h_{i}$ for all $i\in\{0,\ldots,k\}$ extends to a bijection is in $\textsf{L}\cap\textsf{FOLL}$ .

Proof.

For each $(g,h)\in L_{1}\times L_{2}$ , define $X(g,h)=1$ if and only if there exists $(\epsilon_{1},\ldots,\epsilon_{k})\in\{0,1\}^{k}$ such that:

	$\displaystyle g:=g_{0}g_{1}^{\epsilon_{1}}\cdots g_{k}^{\epsilon_{k}},$
	$\displaystyle h:=h_{0}h_{1}^{\epsilon_{1}}\cdots h_{k}^{\epsilon_{k}}.$

Chattophadyay, Torán, and Wagner showed that the cube words for $g$ and $h$ can be computed in $\textsf{L}\cap\textsf{FOLL}$ [CTW13], so $X(g,h)$ is computable in $\textsf{L}\cap\textsf{FOLL}$ . We note that the FOLL bound follows from the fact that $P$ is a balanced parenthesization. As the two quasigroups are the same size, the map on the quasigroups induced by $(g_{0},g_{1},\ldots,g_{k})\mapsto(h_{0},\ldots,h_{k})$ is a well-defined bijection iff the induced map is injective iff the induced map is surjective. So it now suffices to check whether the induced map is surjective. By Lemma 3.2, we may check whether the induced map is surjective in $\textsf{AC}^{0}$ . ∎

Proof of Theorem 3.1.

Let $k=4\lceil\log_{2}(n)\rceil$ . We use $4k^{2}$ non-deterministic bits to guess cube generating sequences $A,B\subseteq L$ and $A^{\prime},B^{\prime}\subseteq L^{\prime}$ , where $A=\{a_{0},a_{1},\ldots,a_{k}\}$ , $B=\{b_{0},b_{1},\ldots,b_{k}\}$ , $A^{\prime}=\{a_{0}^{\prime},a_{1}^{\prime},\ldots,a_{k}^{\prime}\}$ , and $B^{\prime}=\{b_{0}^{\prime},b_{1}^{\prime},\ldots,b_{k}^{\prime}\}$ . We may then in $\textsf{L}\cap\textsf{FOLL}$ check the following.

•

We first check that the map $a_{i}\mapsto a_{i}^{\prime}$ extends to a bijection of $\langle A\rangle$ and $\langle A^{\prime}\rangle$ . In particular, we may check in $\textsf{L}\cap\textsf{FOLL}$ whether $L_{1}=\text{Cube}(A)$ and $L_{2}=\text{Cube}(A^{\prime})$ (see [CTW13, Theorem 5]). The procedure in Lemma 3.3 that decides whether the map $a_{i}\mapsto a_{i}^{\prime}$ for all $i\in\{0,\ldots,k\}$ extends to a bijection $L_{1}\to L_{2}$ , also explicitly computes a bijection $\varphi_{A}:L_{1}\to L_{2}$ if one exists.
•

We proceed analogously for the map $b_{i}\mapsto b_{i}^{\prime}$ for all $i\in\{0,\ldots,k\}$ . In the case that $L_{1}=\text{Cube}(B)$ and $L_{2}=\text{Cube}(B^{\prime})$ , let $\varphi_{B}:L_{1}\to L_{2}$ be the bijection computed by Lemma 3.3.

Suppose now that the bijections $\varphi_{A},\varphi_{B}:L_{1}\to L_{2}$ have been constructed. We now attempt to construct a relation $\varphi_{C}:L_{1}\to L_{2}$ in such a way that $\varphi_{C}$ is a bijection if and only if $(\varphi_{A},\varphi_{B},\varphi_{C})$ is an isotopism. For each pair $(\ell,m)\in L_{1}\times L_{2}$ , define $X(\ell,m)=1$ if and only if we define $\varphi_{C}$ to map $\ell\mapsto m$ . For each $(\epsilon_{1},\ldots,\epsilon_{k}),(\nu_{1},\ldots,\nu_{k})\in\{0,1\}^{k}$ , we do the following:

(a)

Compute:

$\displaystyle g:=a_{0}a_{1}^{\epsilon_{1}}\cdots a_{k}^{\epsilon_{k}},$

$\displaystyle h:=b_{0}b_{1}^{\nu_{1}}\cdots b_{k}^{\nu_{k}}.$

We note that computing $g$ and $h$ can be done in $\textsf{L}\cap\textsf{FOLL}$ (see Chattopadhyay, Toràn, and Wagner [CTW13]).
(b)

Compute $\ell:=gh$ , $\varphi_{A}(g)$ , $\varphi_{B}(h)$ , and $m:=\varphi_{A}(g)\varphi_{B}(h)$ . We set $\varphi_{C}(\ell)=m$ , which we indicate by defining $X(\ell,m)=1$ . The computations at this stage are computable using an $\textsf{AC}^{0}$ circuit.
(c)

It remains to check whether $\varphi_{C}$ is a bijection. By Lemma 3.2, we may test whether $\varphi_{C}$ is a bijection in $\textsf{AC}^{0}$ .

Now $\varphi_{C}$ was constructed so that $(\varphi_{A},\varphi_{B},\varphi_{C})$ satisfies the homotopy condition, so, as they are also bijective, they are an isotopy. Thus, checking whether $L_{1}$ and $L_{2}$ are isotopic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . ∎

Now for any $i,c\geq 0$ , we have that $\beta_{i}\textsf{FO}((\log\log n)^{c})$ cannot compute Parity [CTW13]. As Latin Square Isotopy belongs to $\beta_{2}\textsf{FOLL}$ , we obtain the following corollary.

Corollary 3.4.

For any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to Latin Square Isotopy.

Miller [Mil78] showed that isomorphism testing of Latin square graphs is polynomial-time reducible to the Latin square isotopy problem. Wolf [Wol94] improved this bound, showing that isomorphism testing of Latin square graphs is $\textsf{NC}^{1}$ -reducible to testing for Latin square isotopy. We recall Wolf’s result below.

Lemma 3.5 ([Wol94, Lemma 4.11]).

Let $G$ be a Latin square graph derived from a Latin square of size $n$ . We can retrieve a Latin square from $G$ with a polynomial-sized NC circuit with $O(\log n)$ depth.

Remark 3.6.

The statement of Lemma 4.11 in Wolf actually claims a depth of $O(\log^{2}n)$ . However, in the proof of Lemma 4.11, Wolf shows that only $O(\log n)$ depth is needed [Wol94].

Now by Remark 1.6, we can place the Latin squares into their main isotopy class in $\textsf{AC}^{0}$ . In light of this, Wolf’s result, Theorem 3.1, and Bruck’s result that for $n>23$ , a pseudo-Latin square graph is a Latin square graph [Bru63], we obtain the following corollary.

Corollary 3.7.

Isomorphism of pseudo-Latin square graphs can be decided in $\beta_{2}\textsf{L}$ .

Remark 3.8.

To the best of the author’s knowledge, the largest pseudo-Latin square graph that is not a Latin square graph is the Hall–Janko graph, where $n=10$ (that is, the Hall–Janko graph has $n^{2}=100$ vertices) [Suz69, Nak06]. The author would be grateful for references to larger examples.

We next show that the reduction from [Wol94, Lemma 4.11], which effectively parallelizes the reduction found in [Mil78], can be implemented in $\textsf{AC}^{0}$ . Furthermore, we can place the recovered Latin square into its main isotopy class in $\textsf{AC}^{0}$ (see Remark 1.6). It follows that Latin Square Graph Isomorphism is also in $\beta_{2}\textsf{FOLL}$ . As $\beta_{2}\textsf{FOLL}$ cannot compute Parity, we obtain that for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to Latin Square Graph Isomorphism.

Lemma 3.9.

Let $G$ be a Latin square graph obtained from a Latin square of order $n$ . We can recover a Latin square from $G$ using an $\textsf{AC}^{0}$ circuit.

Proof.

We carefully analyze the reduction from [Mil78, Wol94]. By construction, two vertices $u$ and $v$ in $G$ are adjacent precisely if $u$ and $v$ correspond to elements in the Latin square that are either in the same row, the same column, or have the same value. As a result, each row, each column, and the nodes corresponding to a fixed given value all induce cliques of size $n$ . The algorithm effectively identifies these cliques and their relations to the other cliques in order to recover a Latin square.

Denote $L=(\ell_{ij})_{1\leq i,j\leq n}$ to be the $n\times n$ matrix, which our algorithm will populate with values for the Latin square. We proceed as follows.

1.

We begin by selecting two adjacent vertices $x_{1}$ and $x_{2}$ . Without loss of generality, we may assume $x_{1}$ and $x_{2}$ belong to the same row of the Latin square. We next find the $n$ vertices $v_{1},\ldots,v_{n}$ adjacent to both $x_{1}$ and $x_{2}$ . Precisely, for a vertex $v$ , we have the indicator

$X(v)=E(x_{1},v)\land E(x_{2},v),$

where $E(u,v)=1$ precisely if $u$ and $v$ are adjacent. Exactly $n$ indicators will evaluate to $1$ . All but two of these nodes form a clique of size $n$ with $x_{1}$ and $x_{2}$ . As $v_{1},\ldots,v_{n}$ are adjacent to $x_{1}$ and $x_{2}$ , it suffices to check which $n-2$ vertices of $v_{1},\ldots,v_{n}$ form a clique of size $(n-2)$ . For a given set $S\in\binom{[n]}{n-2}$ , it suffices to check:

$\bigwedge_{\begin{subarray}{c}i,j\in S\\ i\neq j\end{subarray}}E(v_{i},v_{j}),$

which is $\textsf{AC}^{0}$ -computable. There are $\binom{n}{n-2}\in\Theta(n^{2})$ such sets to check. Thus, identifying the clique is $\textsf{AC}^{0}$ -computable.

In parallel, we label the vertices of the clique as $x_{3},\ldots,x_{n}$ . One node not adjacent to any of $x_{3},\ldots,x_{n}$ is labeled $y_{2}$ .
2.

We associate $\ell_{1j}$ with $x_{j}$ . Precisely, we set (in parallel) $\ell_{1j}=j$ for each $j\in[n]$ . This step is $\textsf{AC}^{0}$ -computable.
3.

We next find the $n$ -clique associated with $x_{1}$ and $y_{2}$ , and label the additional vertices as $y_{3},\ldots,y_{n}$ . By similar argument as in Step 1, this step is $\textsf{AC}^{0}$ -computable. Here, we view $x_{1},y_{2},y_{3},\ldots,y_{n}$ as the first column of the Latin square.
4.

For each $3\leq i\leq n$ , there exists a $3\leq j\leq n$ such that $x_{i}$ and $y_{j}$ are adjacent. In particular, as $x_{i}$ and $y_{j}$ are neither in the same row nor the same column, it must be the case that $x_{i}$ and $y_{j}$ correspond to elements in the Latin square with the same value. It follows that our choice of $j$ is in fact unique. We reorder $y_{3},\ldots,y_{n}$ so that $x_{i}$ is adjacent to $y_{i}$ . This step is $\textsf{AC}^{0}$ -computable.
5.

For $2\leq j\leq n$ , we associate $\ell_{j1}$ with $y_{j}$ . Precisely, we set (in parallel), $\ell_{j1}=j$ for each $2\leq j\leq n$ . This step is $\textsf{AC}^{0}$ -computable.
6.
For each of the remaining $(n-1)^{2}$ nodes $z$ , we do the following in parallel:
1. (a)
  
  If $z$ is adjacent to $x_{1}$ , then the edge $\{x_{1},z\}$ is a value edge (as $z$ is not in the same row or column as $x_{1}$ ). So there exist unique $i,j>1$ such that $z$ is adjacent to $x_{j}$ and $y_{i}$ . In this case, we set $\ell_{ij}=1$ . This case is $\textsf{AC}^{0}$ -computable.
2. (b)
  
  Suppose that $z$ is not adjacent to $x_{1}$ . As each row, each column, and each value induce an $n$ -clique, there exist unique $i,j,k\in[n]$ such that $z$ is adjacent to $x_{j},y_{i},x_{k}$ , and $y_{k}$ . Unless $i=j=k$ , we set $\ell_{ij}=k$ . If $i=j=k$ , we do nothing at this step and defer to step 7. This case is $\textsf{AC}^{0}$ -computable.
7.

We note that step 6b does not account for diagonal entries where $\ell_{ii}=i$ . To this end, we do the following. For each $i\geq 2$ , we (in parallel) set $\ell_{ii}$ to be the value that does not appear in row $i$ . This step is $\textsf{AC}^{0}$ -computable.

As we have a finite number of steps, each of which are $\textsf{AC}^{0}$ -computable, it follows that we may recover a Latin square from $G$ using an $\textsf{AC}^{0}$ circuit. ∎

Proposition 3.10.

Isomorphism testing of pseudo-Latin square graphs is in $\beta_{2}\textsf{FOLL}$ . In particular, for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of pseudo-Latin square graphs.

Proof.

We may handle the cases when $n\leq 23$ in $\textsf{AC}^{0}$ . So suppose $n\geq 23$ , and let $G$ and $H$ be pseudo-Latin square graphs. As $n\geq 23$ , we have by Bruck that $G$ and $H$ are Latin square graphs [Bru63]. By Lemma 3.9, we may in $\textsf{AC}^{0}$ recover canonical Latin squares $L_{G}$ and $L_{H}$ corresponding to $G$ and $H$ . Now by [Mil78, Lemma 3], $G\cong H$ if and only if $L_{G}$ and $L_{H}$ are main class isotopic. By Remark 1.6, we may place $L_{G}$ (respectively, $L_{H}$ ) into a normal form corresponding to its main isotopy class in $\textsf{AC}^{0}$ . By Theorem 3.1, we can test whether $L_{G}$ and $L_{H}$ are isotopic in $\beta_{2}\textsf{FOLL}$ . Chattopadhyay, Torán, and Wagner showed that $\beta_{2}\textsf{FOLL}$ cannot compute Parity [CTW13]. The result now follows. ∎

4 Isomorphism Testing of Steiner Designs

In this section, we show that for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of several families of Steiner designs.

4.1 Nets

In this section, we show that for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of nets or the corresponding strongly regular graphs. We note that projective and affine planes are special cases of nets.

Theorem 4.1.

Deciding whether two $k$ -nets are isomorphic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

Proof.

For $k=0,1,2$ , the pair $(k,n)$ determines the net uniquely, and so deciding isomorphism is trivial in these cases. So assume that $n+1\geq k\geq 3$ . Let $\mathcal{N}_{1}(n,k),\mathcal{N}_{2}(n,k)$ be nets. We now start by guessing three non-parallel lines $\ell_{a},\ell_{b},\ell_{c}\in L(\mathcal{N}_{1})$ and three non-parallel lines $\ell_{a}^{\prime},\ell_{b}^{\prime},\ell_{c}^{\prime}\in L(\mathcal{N}_{2})$ . By definition, no two lines in the same parallel class share any points in common, and two lines in different classes share exactly one point in common. As there are $kn$ lines in $\mathcal{N}_{i}$ , we only require $O(\log(kn))$ bits to identify a given line. As $k\leq n+1$ , in fact only $O(\log(n))$ bits are required.

We may identify whether two lines are disjoint in $\textsf{AC}^{0}$ . In particular, we may check in $\textsf{AC}^{0}$ whether $\ell_{a},\ell_{b}$ , and $\ell_{c}$ (respectively, $\ell_{a}^{\prime},\ell_{b}^{\prime}$ , and $\ell_{c}^{\prime}$ ) belong to different parallel classes. Suppose now that $\ell_{a},\ell_{b}$ , and $\ell_{c}$ (respectively, $\ell_{a}^{\prime},\ell_{b}^{\prime}$ , and $\ell_{c}^{\prime}$ ) belong to different parallel classes. As there are $\binom{kn}{2}$ such pairs to check in a given $\mathcal{N}_{i}$ , we may identify in $\textsf{AC}^{0}$ the lines belonging to the three parallel classes $a,b,c$ in each $\mathcal{N}_{i}$ .

Now our three parallel classes determine a net $X_{1}(n,3)$ in $\mathcal{N}_{1}$ and a net $X_{2}(n,3)$ in $\mathcal{N}_{2}$ . We note that a net of degree $3$ identifies a quasigroup (Latin square) up to isomorphism. As Quasigroup Isomorphism is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ [CTW13, Theorem 3.4], we may now in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ decide whether $X_{1}\cong X_{2}$ . We note that [CTW13, Theorem 3.4] actually yields an isomorphism $\varphi:X_{1}\to X_{2}$ . We may now in $\textsf{L}\cap\textsf{FOLL}$ check whether $\varphi$ extends to an isomorphism of $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ . The result follows. ∎

Corollary 4.2.

For any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of two $k$ -nets.

Miller previously showed that isomorphism testing of nets and the corresponding net graphs are equivalent under polynomial-time reductions when $n>(k-1)^{2}$ [Mil78, Theorem 8]. A closer analysis shows that this equivalence holds under $\textsf{TC}^{0}$ -reductions in general; and that when $k$ is bounded, the equivalence holds under $\textsf{AC}^{0}$ -reductions.

Lemma 4.3.

Suppose that $G(V,E)$ is a $k$ -net graph of order $n$ and $n>(k-1)^{2}$ . We can reconstruct the net $\mathcal{N}(n,k)$ associated with $G$ in $\textsf{TC}^{0}$ . If $k$ is bounded, we reconstruct the net $\mathcal{N}(n,k)$ associated with $G$ in $\textsf{AC}^{0}$ .

Proof.

Suppose that $x_{1},x_{2}\in V(G)$ are adjacent. As there are $kn$ lines, it suffices to show that in $\textsf{AC}^{0}$ , we can identify the remaining vertices of $V(G)$ that are on the same line as $x_{1},x_{2}$ . We first note that we can, in $\textsf{AC}^{0}$ , identify the vertices adjacent to both $x_{1}$ and $x_{2}$ .

Let $H$ be the subgraph induced by these vertices together with $x_{1}$ and $x_{2}$ . We note that $H$ contains the maximum clique (of $n$ vertices) containing both $x_{1}$ and $x_{2}$ . The vertices of this clique have degree $n-2$ . As two adjacent vertices have $(n-2)+(k-1)(k-2)$ neighbors in common, there are $(k-1)(k-2)$ vertices of $H$ that do not belong to this clique. Recall that a net has $k$ parallel classes, and any two lines in a given parallel class have empty intersection. Furthermore, two lines from different parallel classes share exactly one point in common. Thus, each nonclique vertex of $H$ is adjacent to exactly $(k-1)$ elements of the clique. Thus, each nonclique vertex of $H$ has degree at most:

(k-1)+(k-1)(k-2)-1=(k-1)^{2}-1.

In general, using the difference in degrees, we may identify the clique and nonclique vertices in $\textsf{TC}^{0}$ . If $k$ is bounded, then we may identify the clique and nonclique vertices in $\textsf{AC}^{0}$ . The result follows. ∎

We combine Lemma 4.3 with Bruck’s result [Bru63, Theorem 7] that for fixed $k$ , pseudo-net graphs with sufficiently many vertices are net graphs to obtain the following.

Corollary 4.4.

For fixed $k$ , isomorphism testing of pseudo-net graphs of order $n$ and degree $k$ is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . In particular, for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of pseudo-net graphs of order $n$ and degree $k$ .

Remark 4.5.

Let $p(x):=(1/2)x^{4}+x^{3}+x^{2}+(3/2)x$ . Bruck [Bru63, Theorem 7] showed that if $n>p(k-1)$ and $k>1$ , then a pseudo-net graph of order $n$ and degree $k$ is a net graph.

4.2 Steiner Triple Systems

Using the standard connection between Steiner triple systems and quasigroups in tandem with [CTW13], we observe the following.

Observation 4.6.

Deciding whether two Steiner triple systems are isomorphic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

Proof.

Let $\mathcal{S}$ be a Steiner triple system of order $n$ . We define a quasigroup $Q$ on the set $[n]$ , with the multiplication operation satisfying the following: (i) for each $x\in[n]$ , define $x^{2}=x$ , and (ii) for each block $\{a,b,c\}$ , define $ab=c$ (note that as the blocks are unordered, all such products $ba=c,ac=ca=b,bc=cb=a$ are required). The Steiner triple system determines $Q$ up to isomorphism. In particular, this construction is $\textsf{AC}^{0}$ -computable. As Quasigroup Isomorphism belongs to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ [CTW13], it follows that deciding whether two Steiner triple systems are isomorphic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . ∎

Proposition 4.7.

Let $G$ be a block-incidence graph on $n$ vertices derived from a Steiner $2$ -design, in which each block has $k$ points and $\sqrt{n}-2>(k-1)^{2}$ . We can reconstruct the Steiner $2$ -design in $\textsf{TC}^{0}$ . Furthermore, if $k$ is bounded, then we may reconstruct the Steiner $2$ -design in $\textsf{AC}^{0}$ .

Proof.

We closely analyze the proof of [Spi96, Proposition 10]. We note that $n$ is the number of blocks in the Steiner design. Let $v$ be the number of points in the Steiner design, and let $R=(v-1)/(k-1)$ be the number of blocks containing a given point. Let $B_{1},B_{2}$ be two blocks that intersect uniquely at the point $p$ . There are $R-2+(k-1)^{2}$ blocks that intersect both $B_{1}$ and $B_{2}$ . We note that $R-2$ of these blocks also go through $p$ , and the remaining $(k-1)^{2}$ blocks go through points other than $p$ .

We note that $p$ corresponds to the edge $\{B_{1},B_{2}\}\in E(G)$ . The $R$ blocks that intersect $p$ (including $B_{1},B_{2}$ ) form a clique. Furthermore, these $R-2$ blocks intersecting $B_{1},B_{2}$ at $p$ do not intersect with the remaining $(k-1)^{2}$ blocks that intersect with $B_{1},B_{2}$ in points other than $p$ . Let $N$ be the set of mutual neighbors for $B_{1},B_{2}$ . Now if $R-2>(k-1)^{2}$ , the $R$ -clique is distinguished from the remaining $(k-1)^{2}$ blocks that don’t contain $p$ by their degrees in the induced subgraph $G[N]$ . We may distinguish these vertices in $\textsf{TC}^{0}$ in general. If $k$ is bounded, then we may distinguish these vertices in $\textsf{AC}^{0}$ .

The fact that $R>\sqrt{n}$ was established in [Spi96, Proposition 10]. ∎

We combine Proposition 4.7 with Bose’s result that pseudo-STS graphs with strictly more than $67$ vertices are STS graphs [Bos63] to obtain the following.

Corollary 4.8.

Deciding whether two pseudo-STS graphs are isomorphic is in $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ . In particular, for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of pseudo-STS graphs.

Remark 4.9.

To the best of the author’s knowledge, it remains open whether the bound of $67$ due to Bose [Bos63] can be decreased.

4.3 Reduction to Steiner $2$ -Designs

Babai & Wilmes [BW13] previously exhibited a reduction from isomorphism testing of Steiner $t$ -designs to the case of Steiner $2$ -designs. A careful analysis shows that their reduction is $\beta_{2}\textsf{AC}^{0}$ -computable. As a corollary, we obtain that GI is not $\textsf{AC}^{0}$ -reducible to isomorphism testing of Steiner $(t,t+1)$ -designs.

Observation 4.10 (c.f. [BW13]).

If isomorphism testing of Steiner $2$ -designs belongs to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ , then testing isomorphism of Steiner $t$ -designs also belongs to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ .

Proof.

Let $\mathcal{D}_{1}=(X_{1},\mathcal{B}_{1},I_{1})$ and $\mathcal{D}_{2}=(X_{2},\mathcal{B}_{2},I_{2})$ be Steiner $(t,k,v)$ -designs. We begin by guessing subsequences $a_{1},\ldots,a_{t-2}\in X_{1}$ and $b_{1},\ldots,b_{t-2}\in X_{2}$ . While we think of $a_{1},\ldots,a_{t-2}$ and $b_{1},\ldots,b_{t-2}$ as determining subsets $A=\{a_{1},\ldots,a_{t-2}\}\subseteq X_{1}$ and $B=\{b_{1},\ldots,b_{t-2}\}\subseteq X_{2}$ , we stress that we guess both the elements and an ordering. As $t\in O(\log n)$ (see the proof of [BW13, Theorem 30], in which Babai & Wilmes cite [RCW75]), guessing $A$ and $B$ requires $O(\log^{2}n)$ bits. We may write down the derived designs $\mathcal{D}_{1}(A)$ and $\mathcal{D}_{2}(B)$ in $\textsf{AC}^{0}$ (see Section 2 for the definition of a derived design).

Suppose first that $\mathcal{D}_{1}\cong\mathcal{D}_{2}$ . Let $\varphi:X_{1}\to X_{2}$ be an isomorphism. Then for any $A\subseteq X_{1}$ of size $t-2$ , the derived designs $\mathcal{D}_{1}(A)$ and $\mathcal{D}_{2}(\varphi(A))$ are isomorphic.

Conversely, let $\psi:X_{1}\setminus A\to X_{2}\setminus B$ be an isomorphism of the derived designs $\mathcal{D}_{1}(A)\cong\mathcal{D}_{2}(B)$ . Define:

\widehat{\psi}(x)=\begin{cases}\psi(x)&:x\not\in A,\\ b_{i}&:x=a_{i}\in A.\end{cases}

We may easily check in $\textsf{AC}^{0}$ whether $\widehat{\psi}$ is an isomorphism of $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ . In particular, if isomorphism testing of Steiner $2$ -designs belongs to $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ , we may use the added non-determinism to guess an isomorphism of $\mathcal{D}_{1}(A)\cong\mathcal{D}_{1}(B)$ that lifts to an isomorphism of $\mathcal{D}_{1}\cong\mathcal{D}_{2}$ . In total, we are still using at most $O(\log^{2}n)$ non-deterministic bits. ∎

We obtain the following corollaries.

Corollary 4.11.

The problem of deciding whether two Steiner $(t,t+1)$ -designs are isomorphic is $\beta_{2}\textsf{AC}^{0}$ -reducible to the problem of finding an isomorphism of two Steiner triple systems.

Now deciding isomorphism testing of Steiner triple systems is $\textsf{AC}^{0}$ -reducible to Quasigroup Isomorphism (see Theorem 4.6). Furthermore, Chattopadhyay, Torán, and Wagner solved the search version of Quasigroup Isomorphism; that is, their $\beta_{2}\textsf{L}\cap\beta_{2}\textsf{FOLL}$ procedure for Quasigroup Isomorphism returns an isomorphism of the two quasigroups whenever an isomorphism exists. So in particular GI is not $\textsf{AC}^{0}$ -reducible to the search version of Quasigroup Isomorphism [CTW13]. We may use the isomorphism for the quasigroups to construct an isomorphism of the Steiner triple systems, which may in turn be used to construct an isomorphism of the two Steiner $(t,t+1)$ -designs. We summarize this observation with the following corollaries.

Corollary 4.12.

The problem of deciding whether two Steiner $(t,t+1)$ -designs are isomorphic is $\beta_{2}\textsf{AC}^{0}$ -reducible to the problem of finding an isomorphism of two quasigroups.

Corollary 4.13.

For any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to the problem of deciding whether two Steiner $(t,t+1)$ -designs are isomorphic.

5 Conference Graphs

In this section, we consider the complexity of identifying conference graphs. A conference graph is a strongly regular graph with parameters $(n,(n-1)/2,(n-5)/4,(n-1)/4)$ . For a graph $G$ , a distinguishing set $S$ is a subset of $V(G)$ such that for every $u,v\in V(G)$ , we have that $u\in S,v\in S$ , or $N(u)\cap S\neq N(v)\cap S$ . We have the following observation.

Observation 5.1.

Let $G$ be a graph, and let $S$ be a distinguishing set. After individualizing each vertex in $S$ , we have that $2$ rounds of the count-free Color Refinement algorithm will assign each vertex in $G$ a unique color.

Babai [Bab80, Lemma 3.2] (take $k=(n-5)/4$ ) showed that conference graphs admit distinguishing sets of size $O(\log n)$ (in fact, almost all such subsets of this size are distinguishing). As a consequence of this and Observation 5.1, we obtain the following.

Theorem 5.2.

Let $G$ be a conference graph, and let $H$ be arbitrary. We can decide isomorphism between $G$ and $H$ in $\beta_{2}\textsf{AC}^{0}$ .

Proof.

We use $m:=O(\log^{2}n)$ non-deterministic bits to guess a sequence $S=(s_{1},\ldots,s_{m})$ for $G$ – while it would suffice for $\{s_{1},\ldots,s_{m}\}$ to be a distinguishing set for $G$ , we only need that after individualizing the elements of $S$ , two rounds of count-free Color Refinement will assign each vertex in $G$ a unique color. There may be non-distinguishing sets that acccomplish this. Let $S^{\prime}=(s_{1}^{\prime},\ldots,s_{m}^{\prime})$ be the vertices of $H$ that were guessed. We now individualize $S$ and $S^{\prime}$ so that $s_{i}\mapsto s_{i}^{\prime}$ get the same color, and $s_{i},s_{j}$ get different colors whenever $i\neq j$ . The individualization step is $\textsf{AC}^{0}$ -computable. We now run two rounds of count-free Color Refinement, which is $\textsf{AC}^{0}$ -computable (c.f., [GV06] and the discussion in Section 2). Lastly, we check that each vertex in $G,H$ has a unique color, and whether the map induced by the colors is an isomorphism. This last step is $\textsf{AC}^{0}$ -computable. The result now follows. ∎

In light of the previous work of Chattopadhyay, Torán, & Wagner [CTW13], we obtain the following corollary.

Corollary 5.3.

For any $i,c\geq 0$ , there is no $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -computable reduction from GI to isomorphism testing of conference graphs.

6 Conclusion

We showed that for any $i,c\geq 0$ , GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to several isomorphism problems characterized by the generator enumeration technique, including Latin Square Isotopy, isomorphism testing of nets (which includes affine and projective planes), isomorphism testing of Steiner $(t,t+1)$ -designs, and isomorphism testing of conference graphs. As a corollary, we obtained that GI is not $\beta_{i}\textsf{FO}((\log\log n)^{c})$ -reducible to isomorphism testing of Latin square graphs, $k$ -net graphs (for fixed $k$ ), and the block-intersection graphs arising from Steiner triple systems. Our work leaves several directions for further research.

In Proposition 4.7, we showed that a Steiner $2$ -design can be recovered from its block-incidence graph in $\textsf{AC}^{0}$ when the block size is bounded. Otherwise, the procedure is $\textsf{TC}^{0}$ -computable, as we need to distinguish vertices by their degrees. As a step towards ruling out $\beta_{i}\textsf{FO}((\log\log n)^{c})$ reductions from GI, it would be of interest to show that we can recover a Steiner $2$ -design from its block-incidence graph in a complexity class that cannot compute Parity. To this end, we ask the following.

Question 6.1.

Can Steiner $2$ -designs of unbounded block size be recovered from their block-incidence graphs in $\textsf{AC}^{0}$ ?

It would also be of interest to find additional families of Steiner $2$ -designs where the isomorphism problem belongs to $\beta_{i}\textsf{FO}((\log\log n)^{c})$ . As a starting point, we ask the following.

Question 6.2.

For Steiner $2$ -designs with bounded block size, can we decide isomorphism in $\beta_{2}\textsf{FOLL}$ ?

While a Steiner $2$ -design $\mathcal{D}$ admits generating set $S$ of $O(\log v)$ points [BL83], we have that $\operatorname{Aut}_{S}(\mathcal{D})$ may in general be non-trivial. This is the key barrier for the techniques here.

Babai & Wilmes [BW13] and Chen, Sun, & Teng [CST13] independently showed that Steiner $2$ -designs admit a set of $O(\log v)$ points where, once individualized, the Color Refinement algorithm assigns a unique color to each point. A priori, it seems plausible that only $\operatorname{poly}\log\log v$ iterations are required. However, Color Refinement takes into account the multiset of colors, and so each round can be implemented with a $\textsf{TC}^{0}$ -circuit. In particular, Babai & Wilmes rely crucially on counting [BW13, Target 2]. So we ask the following.

Question 6.3.

Does there exist an absolute constant $c$ , such that Steiner $2$ -designs admit a set $S$ of $O(\log^{c}v)$ points where, after individuaizing $S$ , the coloring from $\operatorname{poly}\log\log n$ rounds of count-free Color Refinement assigns each point a unique color?

In the remark following the proof of [Bab80, Lemma 3.2], Babai outines a deterministic proof that leverages the greedy set cover algorithm (see [Lov75]) to obtain a distinguishing set of the prescribed size. Now suppose that $G$ and $H$ are isomorphic, and the greedy set cover algorithm returns distinguishing sequences $S$ and $S^{\prime}$ of the same size for $G,H$ respectively. A priori, $S$ and $S^{\prime}$ need not be canonical in the sense that there need not be an isomorphism $\varphi:V(G)\to V(H)$ mapping $\varphi(S)=S^{\prime}$ . Thus, we ask the following.

Question 6.4.

Is it possible to deterministically construct a canonical distinguishing set of the size prescribed by [Bab80, Lemma 3.2] for a graph in polynomial time?

An answer of yes to Question 6.4 in tandem with the work in Section 5 would immediately yield a polynomial-time isomorphism test for conference graphs. Babai’s work [Bab80] implies an $n^{O(\log n)}$ -time algorithm, and to the best of my knowledge, no further improvements have been made to the runtime.

Alternatively, we ask the following.

Question 6.5.

Let $G$ be a conference graph. Does there exists a set of vertices $S$ of size $O(1)$ such that, after individualizing $S$ and running Color Refinement, each vertex of $G$ would receive a unique color?

An answer of yes to Question 6.5 would also yield a polynomial-time isomorphism test for conference graphs, using the individualize-and-refine paradigm. Even finding a such a set $S$ of size $o(\log n)$ would be a major advance, as it would yield an $n^{o(\log n)}$ -time isomorphism test.

References

[AB09] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. 01 2009. doi:10.1017/CBO9780511804090.
[AK06] V. Arvind and Piyush P. Kurur. Graph isomorphism is in SPP. Information and Computation, 204(5):835–852, 2006. doi:10.1016/j.ic.2006.02.002.
[Alb43] A. A. Albert. Quasigroups. I. Transactions of the American Mathematical Society, 54(3):507–519, 1943. doi:10.2307/1990259.
[Bab80] László Babai. On the complexity of canonical labeling of strongly regular graphs. SIAM Journal on Computing, 9(1):212–216, 1980. doi:10.1137/0209018.
[Bab81] Laszlo Babai. On the order of uniprimitive permutation groups. Annals of Mathematics, 113(3):553–568, 1981. doi:10.2307/2006997.
[Bab14] László Babai. On the automorphism groups of strongly regular graphs I. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, page 359–368, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2554797.2554830.
[Bab16] László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684–697. ACM, New York, 2016. Preprint of full version at arXiv:1512.03547v2 [cs.DS]. doi:10.1145/2897518.2897542.
[BE99] Hans Ulrich Besche and Bettina Eick. Construction of finite groups. J. Symb. Comput., 27(4):387–404, 1999. doi:10.1006/jsco.1998.0258.
[BEO02] Hans Ulrich Besche, Bettina Eick, and E.A. O’Brien. A millennium project: Constructing small groups. Intern. J. Alg. and Comput, 12:623–644, 2002. doi:10.1142/S0218196702001115.
[BH92] Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, volume 652 of Lecture Notes in Computer Science, pages 116–127. Springer, 1992. doi:10.1007/3-540-56287-7\_99.
[BKL83] L. Babai, W. M. Kantor, and E. M. Luks. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 162–171, 1983. doi:10.1109/SFCS.1983.10.
[BKLM01] David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, and Pierre McKenzie. On the complexity of some problems on groups input as multiplication tables. J. Comput. Syst. Sci., 63(2):186–200, 2001. doi:10.1006/jcss.2001.1764.
[BL83] László Babai and Eugene M. Luks. Canonical labeling of graphs. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 171–183, New York, NY, USA, 1983. Association for Computing Machinery. doi:10.1145/800061.808746.
[Bos63] R. C. Bose. Strongly regular graphs, partial geometries and partially balanced designs. Pacific Journal of Mathematics, 13(2):389 – 419, 1963. doi:pjm/1103035734.
[Bru63] R. H. Bruck. Finite nets. II. Uniqueness and imbedding. Pacific Journal of Mathematics, 13(2):421 – 457, 1963. doi:10.2140/pjm.1963.13.421.
[BW13] László Babai and John Wilmes. Quasipolynomial-time canonical form for Steiner designs. In STOC 2013, pages 261–270, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488642.
[CC81] Marlene J. Colbourn and Charles J. Colbourn. Concerning the complexity of deciding isomorphism of block designs. Discrete Applied Mathematics, 3(3):155–162, July 1981. doi:10.1016/0166-218X(81)90012-3.
[CFI92] Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992. Originally appeared in SFCS ’89. doi:10.1007/BF01305232.
[CG70] D. G. Corneil and C. C. Gotlieb. An efficient algorithm for graph isomorphism. J. ACM, 17(1):51–64, January 1970. doi:10.1145/321556.321562.
[CH03] John J. Cannon and Derek F. Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symb. Comput., 35:241–267, March 2003. doi:10.1016/S0747-7171(02)00133-5.
[CM80] Marlene J. Colbourn and Rudolf A. Mathon. On cyclic Steiner 2-designs. In C.C. Lindner and A. Rosa, editors, Topics on Steiner Systems, volume 7 of Annals of Discrete Mathematics, pages 215–253. Elsevier, 1980. doi:10.1016/S0167-5060(08)70182-1.
[Col79] M J Colbourn. An analysis technique for Steiner triple systems. Proc. Tenth Southeastern Conf. Combin., Graph Theory, Computing, page 289–303, 1979.
[CST13] Xi Chen, Xiaorui Sun, and Shang-Hua Teng. Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 271–280, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488643.
[CTW13] Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner. Graph isomorphism is not $\rm AC^{0}$ -reducible to group isomorphism. ACM Trans. Comput. Theory, 5(4):Art. 13, 13, 2013. Preliminary version appeared in FSTTCS ’10; ECCC Tech. Report TR10-117. doi:10.1145/2540088.
[ELGO02] Bettina Eick, C. R. Leedham-Green, and E. A. O’Brien. Constructing automorphism groups of $p$ -groups. Comm. Algebra, 30(5):2271–2295, 2002. doi:10.1081/AGB-120003468.
[GV06] Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 3–14. Springer, 2006. doi:10.1007/11786986_2.
[Hub11] Michael Huber. Computational complexity of reconstruction and isomorphism testing for designs and line graphs. Journal of Combinatorial Theory, Series A, 118(2):341–349, 2011. doi:10.1016/j.jcta.2010.06.006.
[IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.
[Kie19] Sandra Kiefer. Power and Limits of the Weisfeiler–Leman Algorithm. PhD thesis, RWTH Aachen University, 2019. URL: https://publications.rwth-aachen.de/record/785831/files/785831.pdf.
[KST92] Johannes Köbler, Uwe Schöning, and Jacobo Torán. Graph isomorphism is low for PP. Comput. Complex., 2:301–330, 1992. doi:10.1007/BF01200427.
[Lad75] Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155–171, January 1975. doi:10.1145/321864.321877.
[LGR16] François Le Gall and David J. Rosenbaum. On the group and color isomorphism problems. arXiv:1609.08253 [cs.CC], 2016.
[Lov75] L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4):383–390, 1975. doi:10.1016/0012-365X(75)90058-8.
[Luk82] Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42–65, 1982. doi:10.1016/0022-0000(82)90009-5.
[Mat79] Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131–136, 1979. doi:10.1016/0020-0190(79)90004-8.
[Mil78] Gary L. Miller. On the $n^{\log n}$ isomorphism technique (a preliminary report). In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pages 51–58, New York, NY, USA, 1978. Association for Computing Machinery. doi:10.1145/800133.804331.
[Nak06] Hiroyuki Nakasora. Mutually orthogonal latin squares and self-complementary designs. Mathematical Journal of Okayama University, 01 2006.
[Neu79] A. Neumaier. Strongly regular graphs with smallest eigenvalue $-m$ . Archiv der Mathematik, 33:392–400, 1979. doi:10.1007/BF01222774.
[NS18] Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 138–150. ACM, 2018. doi:10.1145/3188745.3188900.
[RCW75] Dijen K. Ray-Chaudhuri and Richard M. Wilson. On $t$ -designs. Osaka Journal of Mathematics, 12(3):737–744, 1975. doi:10.18910/7296.
[Ros13] David J. Rosenbaum. Bidirectional collision detection and faster deterministic isomorphism testing. arXiv:1304.3935 [cs.DS], 2013.
[Sch88] Uwe Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312 – 323, 1988. doi:10.1016/0022-0000(88)90010-4.
[SD76] Douglas C. Schmidt and Larry E. Druffel. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. J. ACM, 23(3):433–445, July 1976. doi:10.1145/321958.321963.
[SF21] Tyler Schrock and Rafael Frongillo. Computational complexity of k-block conjugacy. Theoretical Computer Science, 856:21–40, 2021. doi:10.1016/j.tcs.2020.12.009.
[Smo87] Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82. ACM, 1987. doi:10.1145/28395.28404.
[Spi96] Daniel A. Spielman. Faster Isomorphism Testing of Strongly Regular Graphs. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 576–584, New York, NY, USA, 1996. Association for Computing Machinery. doi:10.1145/237814.238006.
[Suz69] Michio Suzuki. A simple group of order $448,345,497,600$ , 1969.
[Tan13] Bangsheng Tang. Towards Understanding Satisfiability, Group Isomorphism and Their Connections. PhD thesis, Tsinghua University, 2013. URL: http://papakonstantinou.org/periklis/pdfs/bangsheng_thesis.pdf.
[Tor04] Jacobo Torán. On the hardness of graph isomorphism. SIAM J. Comput., 33(5):1093–1108, 2004. doi:10.1137/S009753970241096X.
[Vol99] Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. doi:10.1007/978-3-662-03927-4.
[Wil19] James B. Wilson. The threshold for subgroup profiles to agree is logarithmic. Theory of Computing, 15(19):1–25, 2019. doi:10.4086/toc.2019.v015a019.
[Wol94] Marty J. Wolf. Nondeterministic circuits, space complexity and quasigroups. Theoretical Computer Science, 125(2):295–313, 1994. doi:10.1016/0304-3975(92)00014-I.
[ZKT85] V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomorphism problem. Journal of Soviet Mathematics, 29:1426–1481, 1985. doi:10.1007/BF02104746.
[Zoo] Complexity zoo. URL: https://complexityzoo.net.

	$\displaystyle g:=a_{0}a_{1}^{\epsilon_{1}}\cdots a_{k}^{\epsilon_{k}},$
	$\displaystyle h:=b_{0}b_{1}^{\nu_{1}}\cdots b_{k}^{\nu_{k}}.$

On the Complexity of Identifying Strongly Regular Graphs

Abstract

1 Introduction

Theorem 1.1.

Remark 1.2.

Corollary 1.3.

Corollary 1.4.

Remark 1.5.

Remark 1.6.

Theorem 1.7.

Corollary 1.8.

Theorem 1.9.

Remark 1.10.

2 Preliminaries

2.1 Algebra and Combinatorics

2.2 Computational Complexity

Definition 2.1.

2.3 Color Refinement

3 Latin Square Isotopy

Theorem 3.1.

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

Proof of Theorem 3.1.

Corollary 3.4.

Lemma 3.5 ([Wol94, Lemma 4.11]).

Remark 3.6.

Corollary 3.7.

Remark 3.8.

Lemma 3.9.

Proof.

Proposition 3.10.

Proof.

4 Isomorphism Testing of Steiner Designs

4.1 Nets

Theorem 4.1.

Proof.

Corollary 4.2.

Lemma 4.3.

Proof.

Corollary 4.4.

Remark 4.5.

4.2 Steiner Triple Systems

Observation 4.6.

Proof.

Proposition 4.7.

Proof.

Corollary 4.8.

Remark 4.9.

4.3 Reduction to Steiner 22-Designs

Observation 4.10 (c.f. [BW13]).

Proof.

Corollary 4.11.

Corollary 4.12.

Corollary 4.13.

5 Conference Graphs

Observation 5.1.

Theorem 5.2.

Proof.

Corollary 5.3.

6 Conclusion

Question 6.1.

Question 6.2.

Question 6.3.

Question 6.4.

Question 6.5.

References

4.3 Reduction to Steiner $2$ -Designs