- Award ID(s):
- 2047756
- PAR ID:
- 10494301
- Editor(s):
- Guruswami, Venkatesan
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Subject(s) / Keyword(s):
- complexity class tensor isomorphism polynomial isomorphism group isomorphism local operations and classical communication Theory of computation → Algebraic complexity theory
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Kabanets, Valentine (Ed.)In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, 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 Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-groups of class 2 and exponent p. - Despite 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 Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.).more » « less
-
The classical theta correspondence, based on the Weil representation, allows one to lift automorphic representations on symplectic groups or their double covers to au- tomorphic representations on special orthogonal groups. It is of interest to vary the orthog- onal group and describe the behavior in this theta tower (the Rallis tower). In prior work, the authors obtained an extension of the classical theta correspondence to higher degree metaplectic covers of symplectic and special orthogonal groups that is based on the tensor product of the Weil representation with another small representation. In this work we study the existence of generic lifts in the resulting theta tower. In the classical case, there are two orthogonal groups that may support a generic lift of an irreducible cuspidal automorphic representation of a symplectic group. We show that in general the Whittaker range consists of r + 1 groups for the lift from the r-fold cover of a symplectic group. We also give a period criterion for the genericity of the lift at each step of the tower.more » « less
-
A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problems (such as tensor decomposition and tensor PCA), although they are not presented this way, can be viewed as spectral methods on matrices built from simple tensor networks. In this work we leverage the full power of this abstraction to design new algorithms for certain continuous tensor decomposition problems. An important and challenging family of tensor problems comes from orbit recovery, a class of inference problems involving group actions (inspired by applications such as cryo-electron microscopy). Orbit recovery problems over finite groups can often be solved via standard tensor methods. However, for infinite groups, no general algorithms are known. We give a new spectral algorithm based on tensor networks for one such problem: continuous multi-reference alignment over the infinite group SO(2). Our algorithm extends to the more general heterogeneous case.more » « less
-
In this paper we study some classical complexity-theoretic questions regarding G
roup Isomorphism (Gp I). We focus onp -groups (groups of prime power order) with oddp , which are believed to be a bottleneck case for Gp 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 Isomorphism (GI), they had remained open for Gp I, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions withinp -groups of class 2 and exponentp .D
espite the widely held belief thatp -groups of class 2 and exponentp 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 ofp -groups of “small” class and exponentp to those of class two and exponentp .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 Isomorphism -completeness results (Grochow & Qiao, ibid.). -
Müller, Werner ; Shin, Sug Woo ; Templier, Nicolas (Ed.)The classical theta correspondence establishes a relationship between automorphic representations on special orthogonal groups and automorphic representations on symplectic groups or their double covers. This correspondence is achieved by using as integral kernel a theta series on the metaplectic double cover of a symplectic group that is constructed from the Weil representation. There is also an analogous local correspondence. In this work we present an extension of the classical theta correspondence to higher degree metaplectic covers of symplectic and special orthogonal groups. The key issue here is that for higher degree covers there is no analogue of the Weil representation, and additional ingredients are needed. Our work reflects a broader paradigm: constructions in automorphic forms that work for algebraic groups or their double covers should often extend to higher degree metaplectic covers.more » « less