Details

Autor(en) / Beteiligte

• Fernau, Henning
• Jansen, Klaus

Titel

On the Parallel Complexity of Group Isomorphism via Weisfeiler–Leman

Ist Teil von

• Fundamentals of Computation Theory, 2023, Vol.14292, p.234-247

Ort / Verlag

Switzerland: Springer

Erscheinungsjahr

2023

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In this paper, we show that the constant-dimensional Weisfeiler–Leman algorithm for groups (Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity upper bounds on isomorphism testing for several families of groups. In particular, we show:Groups with an Abelian normal Hall subgroup whose complement is O(1)-generated are identified by constant-dimensional Weisfeiler–Leman using only a constant number of rounds. This places isomorphism testing for this family of groups into L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {L}$$\end{document}; the previous upper bound for isomorphism testing was P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{P}$$\end{document} (Qiao, Sarma, & Tang, STACS 2011).We use the individualize-and-refine paradigm to obtain a quasiSAC1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {quasiSAC}^{1}$$\end{document} isomorphism test for groups without Abelian normal subgroups, previously only known to be in P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{P}$$\end{document} (Babai, Codenotti, & Qiao, ICALP 2012).We extend a result of Brachter & Schweitzer (ESA, 2022) on direct products of groups to the parallel setting. Namely, we also show that Weisfeiler–Leman can identify direct products in parallel, provided it can identify each of the indecomposable direct factors in parallel. They previously showed the analogous result for P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{P}$$\end{document}. We finally consider the count-free Weisfeiler–Leman algorithm, where we show that count-free WL is unable to even distinguish Abelian groups in polynomial-time. Nonetheless, we use count-free WL in tandem with bounded non-determinism and limited counting to obtain a new upper bound of β1MAC0(FOLL)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _{1}\textsf {MAC}^{0}(\textsf {FOLL})$$\end{document} for isomorphism testing of Abelian groups. This improves upon the previous TC0(FOLL)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {TC}^{0}(\textsf {FOLL})$$\end{document} upper bound due to Chattopadhyay, Torán, & Wagner (ACM Trans. Comput. Theory, 2013).