On the Complexity of Identifying Strongly Regular Graphs

In this paper, we show that Graph Isomorphism (GI) is not ${\mathsf{\text{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 ${\mathsf{\text{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\mathsf{\text{FOLL}}$, which cannot compute Parity (Chattopadhyay, Torán, & Wagner, ACM Trans. Comp. Theory, 2013).