More Like this

1. Leibniz International Proceedings in Informatics (LIPIcs):15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

   https://doi.org/10.4230/LIPIcs.ITCS.2024.31  

   Chen, Zhili; Grochow, Joshua A.; Qiao, Youming; Tang, Gang; Zhang, Chuanqi (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   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
2. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits

   https://doi.org/10.1145/3406325.3451096  

   Bhargava, Vishwas; Saraf, Shubhangi; Volkovich, Ilya (June 2021, STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’). 

   more » « less
3. KRONECKER PRODUCT OF TENSORS AND HYPERGRAPHS, STRUCTURE AND DYNAMICS

   PICKARD, J; CHEN, C; STANSBURY, C; SURANA, A; BLOCH, A; RAJAPAKSE, I (May 2024, SIAM Journal Matrix Analysis and Applications)

   Hypergraphs and tensors extend classic graph and matrix theories to account for multiway relationships, which are ubiquitous in engineering, biological, and social systems. While the Kronecker product is a potent tool for analyzing the coupling of systems in a graph or matrix context, its utility in studying multiway interactions, such as those represented by tensors and hypergraphs, remains elusive. In this article, we present a comprehensive exploration of algebraic, structural, and spectral properties of the tensor Kronecker product. We express Tucker and tensor train decompositions and various tensor eigenvalues in terms of the tensor Kronecker product. Additionally, we utilize the tensor Kronecker product to form Kronecker hypergraphs, which are tensor-based hypergraph products, and investigate the structure and stability of polynomial dynamics on Kronecker hypergraphs. Finally, we provide numerical examples to demonstrate the utility of the tensor Kronecker product in computing Z-eigenvalues, performing various tensor decompositions, and determining the stability of polynomial systems. 

   more » « less
4. Misiurewicz polynomials and dynamical units, part II

   https://doi.org/10.1007/s40993-024-00539-0  

   Benedetto, Robert_L; Goksel, Vefa (June 2024, Research in Number Theory)

   Abstract Fix an integer$$d\ge 2$$ $d\ge 2$. The parameters$$c_0\in \overline{\mathbb {Q}}$$ $c_0\in \overline{Q}$for which the unicritical polynomial$$f_{d,c}(z)=z^d+c\in \mathbb {C}[z]$$ $f_{d,c}\left(z\right)=z^d+c\in C\left[z\right]$has finite postcritical orbit, also known asMisiurewiczparameters, play a significant role in complex dynamics. Recent work of Buff, Epstein, and Koch proved the first known cases of a long-standing dynamical conjecture of Milnor using their arithmetic properties, about which relatively little is otherwise known. Continuing our work from a companion paper, we address further arithmetic properties of Misiurewicz parameters, especially the nature of the algebraic integers obtained by evaluating the polynomial defining one such parameter at a different Misiurewicz parameter. In the most challenging such combinations, we describe a connection between such algebraic integers and the multipliers of associated periodic points. As part of our considerations, we also introduce a new class of polynomials we callp-special, which may be of independent number theoretic interest. 

   more » « less
5. Geometry and arithmetic of crystallographic sphere packings

   https://doi.org/10.1073/pnas.1721104116  

   Kontorovich, Alex; Nakamura, Kei (December 2018, Proceedings of the National Academy of Sciences)

   We introduce the notion of a “crystallographic sphere packing,” defined to be one whose limit set is that of a geometrically finite hyperbolic reflection group in one higher dimension. We exhibit an infinite family of conformally inequivalent crystallographic packings with all radii being reciprocals of integers. We then prove a result in the opposite direction: the “superintegral” ones exist only in finitely many “commensurability classes,” all in, at most, 20 dimensions. 

   more » « less