Zobrazeno 1 - 10
of 46
pro vyhledávání: '"Levet, Michael"'
Autor:
Bailey, Lora, Blake, Heather Smith, Cochran, Garner, Fox, Nathan, Levet, Michael, Mahmoud, Reem, Singgih, Inne, Stadnyk, Grace, Wiedemann, Alexander
Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming
Externí odkaz:
http://arxiv.org/abs/2402.01942
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their m
Externí odkaz:
http://arxiv.org/abs/2402.00133
Autor:
Grochow, Joshua A., Levet, Michael
Publikováno v:
EPTCS 390, 2023, pp. 185-202
In this paper, 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
Externí odkaz:
http://arxiv.org/abs/2310.01007
In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in $\textsf{TC}^{2}$. Our approach builds on the framework of K\"obler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded tre
Externí odkaz:
http://arxiv.org/abs/2306.17777
In this paper, we consider the moments of statistics on conjugacy classes of the colored permutation groups $\mathfrak{S}_{n,r}=\mathbb{Z}_r\wr \mathfrak{S}_n$. We first show that any fixed moment coincides on all conjugacy classes where all cycles h
Externí odkaz:
http://arxiv.org/abs/2305.11800
Autor:
Bailey, Lora, Blake, Heather Smith, Cochran, Garner, Fox, Nathan, Levet, Michael, Mahmoud, Reem, Matson, Elizabeth, Singgih, Inne, Stadnyk, Grace, Wang, Xinyi, Wiedemann, Alexander
Publikováno v:
Theoretical Computer Science (2024)
In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010)
Externí odkaz:
http://arxiv.org/abs/2305.01851
In this paper, we show that the $(3k+4)$-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O(\log n)$ rounds. This improves the result of Grohe & Verbitsky (ICALP 2006), who previously established the analogous result f
Externí odkaz:
http://arxiv.org/abs/2303.07985
Autor:
Loth, Jesse Campion, Levet, Michael, Liu, Kevin, Stucky, Eric Nathan, Sundaram, Sheila, Yin, Mei
We introduce the notion of a weighted inversion statistic on the symmetric group, and examine its distribution on each conjugacy class. Our work generalizes the study of several common permutation statistics, including the number of inversions, the n
Externí odkaz:
http://arxiv.org/abs/2301.00898
Autor:
Collins, Nathaniel A., Levet, Michael
We investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & Schweitzer, LICS 2020) in tandem with limited non-determinism and limited counting
Externí odkaz:
http://arxiv.org/abs/2212.11247
Autor:
Grochow, Joshua A., Levet, Michael
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fra\"iss\'e bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) heirarchy. This is a Spoiler-Duplicator game in wh
Externí odkaz:
http://arxiv.org/abs/2209.13725