On the Combinatorial and Logical Complexities of Algebraic Structures / Michael Levet.
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 WeisfeilerLeman algorithm for groups (Brachter & Schweitzer...
Saved in:
Online Access: 
Connect to online resource 

Main Author:  
Format:  Thesis Electronic eBook 
Language:  English 
Published: 
Ann Arbor :
ProQuest Dissertations & Theses,
2023

Subjects: 
MARC
LEADER  00000nam a22000003i 4500  

001  in00000015323  
006  m d  
007  cr un  
008  230821s2023 miusm eng d  
005  20230828203110.9  
020  a 9798379529178  
035  a (MiAaPQD)AAI30418002  
035  a AAI30418002  
040  a MiAaPQD b eng c MiAaPQD e rda  
100  1  a Levet, Michael, e author.  
245  1  0  a On the Combinatorial and Logical Complexities of Algebraic Structures / c Michael Levet. 
264  1  a Ann Arbor : b ProQuest Dissertations & Theses, c 2023  
300  a 1 electronic resource (205 pages)  
336  a text b txt 2 rdacontent  
337  a computer b c 2 rdamedia  
338  a online resource b cr 2 rdacarrier  
500  a Source: Dissertations Abstracts International, Volume: 8411, Section: B.  
500  a Advisors: Grochow, Joshua A. Committee members: Alm, Jeremy F.; Mayr, Peter; Trivedi, Ashutosh; Sankaranarayanan, Sriram.  
502  b Ph.D. c University of Colorado at Boulder d 2023.  
506  a This item is not available from ProQuest Dissertations & Theses.  
520  a 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 WeisfeilerLeman 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 countfree WeisfeilerLeman algorithm is unable to even identify Abelian groups. As a consequence, we obtain that FO fails to capture all polynomialtime computable queries even on Abelian groups. Nonetheless, we leverage the countfree variant of Weisfeiler Leman in tandem with bounded nondeterminism and limited counting to obtain a new upper bound of β1MAC0 (FOLL) for isomorphism testing of Abelian groups. This improves upon the previous TC0 (FOLL) upper bound due to Chattopadhyay, Toran, & Wagner (ACM Trans. Comput. Theory, 2013).WeisfeilerLeman is equivalent to the first in a hierarchy of EhrenfeuchtFraisse 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 EhrenfeuchtFraisse bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) hierarchy. This is a SpoilerDuplicator 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 WeisfeilerLeman (WL) coloring, which we call 2ary WL. We then show that the 2ary WL is equivalent to the second EhrenfeuchtFraisse 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 firstorder logic with generalized 2ary quantifiers, using only O(1) variables and O(1) quantifier depth.In Chapter 5, we show that Graph Isomorphism (GI) is not AC0 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 AC0 reducible to isomorphism testing of Latin square graphs and strongly regular graphs arising from special cases of Steiner 2designs. We accomplish this by showing that the generatorenumeration technique for each of these problems can be implemented in β2FOLL, which cannot compute Parity (Chattopadhyay, Toran, & Wagner, ibid.).Finally, in Chapter 6, we shed new light on the spectrum of the relation algebra we call An, which is obtained by splitting the nonflexible diversity atom of 67 into n symmetric atoms. Precisely, we show that the minimum value in Spec(An) is at most 2n6+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 2n2 + Ω(n √ log n). Prior to the work in this thesis, only the trivial bound of n2 + 2n + 3 was known.  
546  a English  
590  a School code: 0051  
650  4  a Computer science.  
650  4  a Mathematics.  
653  a Flexible atom conjecture  
653  a Graph isomorphism  
653  a Group isomorphism  
653  a Relation algebras  
653  a Stronglyregular graphs  
653  a WeisfeilerLeman  
655  a Theses x CU Boulder x Computer Science. 2 local.  
700  1  a Grochow, Joshua A. e degree supervisor.  
773  0  t Dissertations Abstracts International g 8411B.  
791  a Ph.D.  
792  a 2023  
856  4  0  z Connect to online resource u https://colorado.idm.oclc.org/login?url=http://gateway.proquest.com/openurl?url_ver=Z39.882004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:30418002 
999  f  f  s af109519b17142c29882d8f391eabfab i 428ab3d7c8a541978d4f21d14b2ddbaa 
952  f  f  p Can circulate a University of Colorado Boulder b Online c Online d Online i web 