On the Combinatorial and Logical Complexities of Algebraic Structures

Levet, Michael

Graduate Thesis Or Dissertation

On the Combinatorial and Logical Complexities of Algebraic Structures Public Deposited

Analytics

Download PDF

Citations

Citeable URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/8p58pf525

Abstract

In this thesis, we investigate the combinatorial and logical complexities of several algebraic structures, including groups, quasigroups, certain families of strongly regular graphs, and relation algebras. In Chapter 3, we leverage the Weisfeiler–Leman algorithm for groups (Brachter & Schweitzer, LICS 2020) to improve the parallel complexity of isomorphism testing for several families of groups including (i) coprime extensions H ⋉ N where H is O(1)-generated and N is Abelian (c.f., Qiao, Sarma, & Tang, STACS 2011), (ii) direct product decompositions, and (iii) groups without Abelian normal subgroups (c.f., Babai, Codenotti, & Qiao, ICALP 2012). Furthermore, we show that the weaker count-free Weisfeiler–Leman algorithm is unable to even identify Abelian groups. As a consequence, we obtain that FO fails to capture all polynomial-time computable queries even on Abelian groups. Nonetheless, we leverage the count-free variant of Weisfeiler– Leman in tandem with bounded non-determinism and limited counting to obtain a new upper bound of β₁MAC⁰ (FOLL) for isomorphism testing of Abelian groups. This improves upon the previous TC⁰ (FOLL) upper bound due to Chattopadhyay, Toran, & Wagner (ACM Trans. Comput. Theory, 2013).

Weisfeiler–Leman is equivalent to the first in a hierarchy of Ehrenfeucht–Fra¨ıss´e pebble games (Hella, Ann. Pur. Appl. Log., 1989). In Chapter 4, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fra¨ıss´e bijective pebble game in Hella’s (Ann. Pure Appl. Log., 1989) hierarchy. This is a Spoiler-Duplicator game in which Spoiler can place up to two pebbles each round. While it trivially solves graph isomorphism, it may be nontrivial for finite groups, and other ternary relational structures. We first provide a novel generalization of Weisfeiler-Leman (WL) coloring, which we call 2-ary WL. We then show that the 2-ary WL is equivalent to the second Ehrenfeucht-Fra¨ıss´e bijective pebble game in Hella’s hierarchy.

Our main result is that, in the pebble game characterization, only O(1) pebbles and O(1) rounds are sufficient to identify all groups without Abelian normal subgroups. In particular, we show that within the first few rounds, Spoiler can force Duplicator to select an isomorphism between two such groups at each subsequent round. By Hella’s results (ibid.), this is equivalent to saying that these groups are identified by formulas in first-order logic with generalized 2-ary quantifiers, using only O(1) variables and O(1) quantifier depth.

In Chapter 5, we show that Graph Isomorphism (GI) is not AC⁰ -reducible to several problems, including the Latin Square Isotopy problem and isomorphism testing of several families of Steiner designs. As a corollary, we obtain that GI is not AC⁰ -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 β₂FOLL, which cannot compute Parity (Chattopadhyay, Tor´an, & Wagner, ibid.).

Finally, in Chapter 6, we shed new light on the spectrum of the relation algebra we call A_n, which is obtained by splitting the non-flexible diversity atom of 6₇ into n symmetric atoms. Precisely, we show that the minimum value in Spec(A_n) is at most 2n^6+o(1), which is the first polynomial bound and improves upon the previous bound due to Dodd & Hirsch (J. Relat. Methods Comput. Sci. 2013). We also improve the lower bound to 2n² + Ω(n√logn). Prior to the work in this thesis, only the trivial bound of n² + 2n + 3 was known.

Creator