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 Weisfeiler-Leman 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 miu|||||sm |||| ||eng d | ||
| 005 | 20250318200621.7 | ||
| 020 | |a 9798379529178 | ||
| 035 | |a (MiAaPQD)AAI30418002 | ||
| 035 | |a AAI30418002 | ||
| 040 | |a MiAaPQD |b eng |e rda |c MiAaPQD | ||
| 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 | ||
| 506 | |a This item is not available from ProQuest Dissertations & Theses. | ||
| 590 | |a School code: 0051 | ||
| 500 | |a Source: Dissertations Abstracts International, Volume: 84-11, 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. | ||
| 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 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 β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).Weisfeiler-Leman is equivalent to the first in a hierarchy of Ehrenfeucht-Fraisse 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-Fraisse 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-Fraisse 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 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 2-designs. We accomplish this by showing that the generator-enumeration 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 non-flexible 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 | ||
| 655 | 7 | |a Theses |x CU Boulder |x Computer Science. |2 local | |
| 650 | 0 | |a Computer science. |0 http://id.loc.gov/authorities/subjects/sh89003285 | |
| 650 | 0 | |a Mathematics. |0 http://id.loc.gov/authorities/subjects/sh85082139 | |
| 653 | |a Flexible atom conjecture | ||
| 653 | |a Graph isomorphism | ||
| 653 | |a Group isomorphism | ||
| 653 | |a Relation algebras | ||
| 653 | |a Strongly-regular graphs | ||
| 653 | |a Weisfeiler--Leman | ||
| 700 | 1 | |a Grochow, Joshua A., |e degree supervisor. | |
| 773 | 0 | |t Dissertations Abstracts International |g 84-11B. | |
| 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.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:30418002 |
| 944 | |a MARS - RDA ENRICHED | ||
| 956 | |a ETD | ||
| 999 | f | f | |s af109519-b171-42c2-9882-d8f391eabfab |i 428ab3d7-c8a5-4197-8d4f-21d14b2ddbaa |
| 952 | f | f | |p Can circulate |a University of Colorado Boulder |b Online |c Online |d Online |i web |