On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors

Grochow, JA; Qiao, Y

On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors

Grochow, JA Qiao, Y

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: ACM Transactions on Computation Theory

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (852.67 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Grochow, JA
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.date.accessioned	2024-02-06T10:29:35Z
dc.date.available	2024-02-06T10:29:35Z
dc.identifier.citation	ACM Transactions on Computation Theory
dc.identifier.issn	1942-3454
dc.identifier.issn	1942-3462
dc.identifier.uri	http://hdl.handle.net/10453/175382
dc.description.abstract	<jats:p> In this paper we study some classical complexity-theoretic questions regarding G <jats:sc>roup</jats:sc> I <jats:sc>somorphism</jats:sc> (G <jats:sc>p</jats:sc> I). We focus on <jats:italic>p</jats:italic> -groups (groups of prime power order) with odd <jats:italic>p</jats:italic> , which are believed to be a bottleneck case for G <jats:sc>p</jats:sc> I, and work in the model of matrix groups over finite fields. Our main results are as follows. </jats:p> <jats:p> <jats:list list-type="bullet"> <jats:list-item> <jats:label>•</jats:label> <jats:p> Although search-to-decision and counting-to-decision reductions have been known for over four decades for G <jats:sc>raph</jats:sc> I <jats:sc>somorphism</jats:sc> (GI), they had remained open for G <jats:sc>p</jats:sc> I, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from T <jats:sc>ensor</jats:sc> I <jats:sc>somorphism</jats:sc> (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within <jats:italic>p</jats:italic> -groups of class 2 and exponent <jats:italic>p</jats:italic> . </jats:p> </jats:list-item> <jats:list-item> <jats:label>•</jats:label> <jats:p> D <jats:sc>espite</jats:sc> the widely held belief that <jats:italic>p</jats:italic> -groups of class 2 and exponent <jats:italic>p</jats:italic> are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of <jats:italic>p</jats:italic> -groups of “small” class and exponent <jats:italic>p</jats:italic> to those of class two and exponent <jats:italic>p</jats:italic> . </jats:p> </jats:list-item> </jats:list> </jats:p> <jats:p> For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of <jats:sc>GI</jats:sc> . Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. </jats:p> <jats:p>The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis</jats:p> <jats:p> of the Lazard correspondence with T <jats:sc>ensor</jats:sc> I <jats:sc>somorphism</jats:sc> -completeness results (Grochow & Qiao, ibid.). </jats:p>
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation.ispartof	ACM Transactions on Computation Theory
dc.relation.isbasedon	10.1145/3625308
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	“©ACM2023. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 24 September 2023 http://doi.acm.org/10.1145/3625308”
dc.subject	0102 Applied Mathematics, 0802 Computation Theory and Mathematics
dc.subject.classification	4602 Artificial intelligence
dc.subject.classification	4613 Theory of computation
dc.subject.classification	4901 Applied mathematics
dc.title	On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors
dc.type	Journal Article
utslib.for	0102 Applied Mathematics
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2024-02-06T10:29:34Z
pubs.publication-status	Published online

Abstract:

In this paper we study some classical complexity-theoretic questions regarding G roup I somorphism (G p I). We focus on p -groups (groups of prime power order) with odd p , which are believed to be a bottleneck case for G p I, and work in the model of matrix groups over finite fields. Our main results are as follows.

• Although search-to-decision and counting-to-decision reductions have been known for over four decades for G raph I somorphism (GI), they had remained open for G p I, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from T ensor I somorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p -groups of class 2 and exponent p .

• D espite the widely held belief that p -groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of p -groups of “small” class and exponent p to those of class two and exponent p .

For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI . Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard correspondence with T ensor I somorphism -completeness results (Grochow & Qiao, ibid.).

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/175382