skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Leibniz International Proceedings in Informatics (LIPIcs):15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d >= 3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.  more » « less
Award ID(s):
2047756
PAR ID:
10494301
Author(s) / Creator(s):
; ; ; ;
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
  1. 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
  2. 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
  3. 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
  4. In this paper we study some classical complexity-theoretic questions regarding GroupIsomorphism(GpI). We focus onp-groups (groups of prime power order) with oddp, 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 GraphIsomorphism(GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from TensorIsomorphism(Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions withinp-groups of class 2 and exponentp.

    Despitethe widely held belief thatp-groups of class 2 and exponentpare 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 exponentpto 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 ofGI. 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 TensorIsomorphism-completeness results (Grochow & Qiao, ibid.).

     
    more » « less
  5. 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