On the Algebraic Proof Complexity of Tensor Isomorphism
Article No.: 4, Pages 1 - 40
Abstract
The Tensor Isomorphism problem (TI) has recently emerged as having connections to multiple areas of research within complexity and beyond, but the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, TI (or rather, proving that two tensors are non-isomorphic) lends itself very naturally to algebraic and semi-algebraic proof systems, such as the Polynomial Calculus (PC) and Sum of Squares (SoS). For its combinatorial cousin Graph Isomorphism, essentially optimal lower bounds are known for approaches based on PC and SoS (Berkholz & Grohe, SODA '17). Our main results are an Ω(n) lower bound on PC degree or SoS degree for Tensor Isomorphism, and a nontrivial upper bound for testing isomorphism of tensors of bounded rank.
We also show that PC cannot perform basic linear algebra in sub-linear degree, such as comparing the rank of two matrices (which is essentially the same as 2-TI), or deriving BA = I from AB = I. As linear algebra is a key tool for understanding tensors, we introduce a strictly stronger proof system, PC+Inv, which allows as derivation rules all substitution instances of the implication AB = I → BA = I. We conjecture that even PC+Inv cannot solve TI in polynomial time either, but leave open getting lower bounds on PC+Inv for any system of equations, let alone those for TI. We also highlight many other open questions about proof complexity approaches to TI.
References
[1]
Manindra Agrawal and Nitin Saxena. Automorphisms of finite rings and applications to complexity of problems. In STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings, pages 1--17, 2005.
[2]
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM J. Comput., 34(1):67--88, 2004.
[3]
Albert Atserias and Elitza N. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput., 42(1):112--137, 2013.
[4]
László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In STOC'16 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684--697. ACM, New York, 2016.
[5]
Eli Ben-Sasson and Russell Impagliazzo. Random CNF's are hard for the Polynomial Calculus. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17--18 October, 1999, New York, NY, USA, pages 415--421. IEEE Computer Society, 1999. (Journal version in Comput. Complex. 2010, ).
[6]
Christoph Berkholz. The relation between polynomial calculus, sherali-adams, and sum-of-squares proofs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[7]
Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6--10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 155--166. Springer, 2015.
[8]
Christoph Berkholz and Martin Grohe. Linear diophantine equations, group csps, and graph isomorphism. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16--19, pages 327--339. SIAM, 2017. Preprint arXiv:1607.04287 [cs.CC].
[9]
Jendrik Brachter and Pascal Schweitzer. On the Weisfeiler-Leman dimension of finite groups. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8--11, 2020, pages 287--300. ACM, 2020.
[10]
Jendrik Brachter and Pascal Schweitzer. A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5--9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 27:1--27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
[11]
R. P. Brent. Algorithms for matrix multiplication. Stanford Computer Science Dept. Tech. Report STAN-CS-70-157, available online at https://apps.dtic.mil/sti/pdfs/AD0705509.pdf, 1970.
[12]
Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, and James B. Wilson. Incorporating Weisfeiler-Leman into algorithms for group isomorphism. arXiv:1905.02518 [cs.CC], 2019.
[13]
Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, and Toniann Pitassi. Homogenization and the polynomial calculus. Comput. Complex., 11(3--4):91--108, 2002.
[14]
Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi. Linear gaps between degrees for the polynomial calculus modulo distinct primes. J. Comput. Syst. Sci., 62(2):267--289, 2001.
[15]
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389--410, 1992.
[16]
Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. In Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pages 174--183. ACM, New York, 1996.
[17]
Nathaniel A. Collins and Michael Levet. Count-free Weisfeiler-Leman and group isomorphism. arXiv:2212.11247 [cs.DS], 2022.
[18]
Jean-Charles Faugère and Ludovic Perret. Polynomial equivalence problems: Algorithmic and theoretical aspects. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 -- June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 30--47. Springer, 2006.
[19]
Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk. Wildness for tensors. Linear Algebra Appl., 566:212--244, 2019.
[20]
D. Ju. Grigoriev. Complexity of "wild" matrix problems and of the isomorphism of algebras and graphs. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 105:10--17, 198, 1981. Theoretical applications of the methods of mathematical logic, III.
[21]
Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1--2):613--622, 2001.
[22]
Dima Grigoriev. Polynomial complexity of solving systems of few algebraic equations with small degrees. In Vladimir P. Gerdt, Wolfram Koepf, Ernst W. Mayr, and Evgenii V. Vorozhtsov, editors, Computer Algebra in Scientific Computing - 15th International Workshop, CASC 2013, Berlin, Germany, September 9--13, 2013. Proceedings, volume 8136 of Lecture Notes in Computer Science, pages 136--139. Springer, 2013.
[23]
Joshua A. Grochow. Matrix Lie algebra isomorphism. In IEEE Conference on Computational Complexity (CCC12), pages 203--213, 2012. Also available as arXiv:1112.2012 [cs.CC] and ECCC Technical Report TR11-168.
[24]
Joshua A. Grochow. Answer to "deciding bound on tensor rank for a fixed value". CSTheory StackExchange, https://cstheory.stackexchange.com/a/19518/129, 2013.
[25]
Joshua A. Grochow and Youming Qiao. On p-group isomorphism: Search-to-decision, counting-to-decision, and nilpotency class reductions via tensors. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20--23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 16:1--16:38. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[26]
Joshua A. Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials I: tensor isomorphism-completeness. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6--8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 31:1--31:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[27]
Xiaoyu He and Youming Qiao. On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions. European J. Combin., 98:Paper No. 103404, 12, 2021.
[28]
Harald Andrés Helfgott. Isomorphismes de graphes en temps quasi-polynomial [d'après Babai et Luks, Weisfeiler-Leman,...]. Astérisque, (407):Exp. No. 1125, 135--182, 2019. Séminaire Bourbaki. Vol. 2016/2017. Exposés 1120--1135. English translation with appendices by Jitendra Bajpai and Daniele Dona available at arXiv:17010.04574 [math.GR].
[29]
Pavel Hrubes and Iddo Tzameret. Short proofs for the determinant identities. SIAM J. Comput., 44(2):340--383, 2015.
[30]
Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General linear group action on tensors: A candidate for post-quantum cryptography. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1--5, 2019, Proceedings, Part I, volume 11891 of Lecture Notes in Computer Science, pages 251--281. Springer, 2019. Preprint arXiv:1906.04330 [cs.CR].
[31]
J. M. Landsberg. Tensors: geometry and applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.
[32]
Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796--817, 2000/01.
[33]
Thomas Lehmkuhl and Thomas Lickteig. On the order of approximation in approximative triadic decompositions of tensors. Theoret. Comput. Sci., 66(1):1--14, 1989.
[34]
Thomas Lickteig. Typical tensorial rank. Linear Algebra Appl., 69:95--120, 1985.
[35]
Eugene M. Luks. Permutation groups and polynomial-time computation. In Groups and computation (New Brunswick, NJ, 1991), volume 11 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 139--175. Amer. Math. Soc., Providence, RI, 1993.
[36]
Brendan D. McKay. Practical graph isomorphism. Congr. Numer., 30:45--87, 1981.
[37]
Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symbolic Comput., 60:94--112, 2014.
[38]
Takunari Miyazaki. Luks's reduction of graph isomorphism to code equivalence. Comment to E. W. Clark, https://groups.google.com/forum/#!msg/sci.math.research/puZxGj9HXKI/CeyH2yyyNFUJ, 1996.
[39]
Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry Vetrov. Tensorizing neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS'15, pages 442--450. MIT Press, 2015.
[40]
Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5--7, 2014, pages 1659--1677. SIAM, 2014. Preprint available as arXiv:1401.2436 [cs.CC].
[41]
Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12--16, 1996, Proceeding, pages 33--48, 1996.
[42]
Erez Petrank and Ron M. Roth. Is code equivalence easy to decide? IEEE Trans. Inf. Theory, 43(5):1602--1604, 1997.
[43]
Alexander A. Razborov. Lower bounds for the polynomial calculus. Comput. Complex., 7(4):291--324, 1998.
[44]
Grant Schoenebeck. Linear level lasserre lower bounds for certain k-csps. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593--602. IEEE, 2008.
[45]
Aaron Snook, Grant Schoenebeck, and Paolo Codenotti. Graph Isomorphism and the Lasserre hierarchy. arXiv:1401.0758 [cs.CC], 2014.
[46]
Michael Soltys. The complexity of derivations of matrix identities. PhD thesis, University of Toronto, 2001. Availalble on ECCC at https://eccc.weizmann.ac.il/resources/pdf/soltys.pdf.
[47]
Michael Soltys and Stephen Cook. The proof complexity of linear algebra. Ann. Pure Appl. Logic, 130(1--3):277--323, 2004.
[48]
Martín Sombra. A sparse effective Nullstellensatz. Adv. in Appl. Math., 22(2):271--295, 1999.
[49]
Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, and Willy Susilo. Practical post-quantum signature schemes from isomorphism problems of trilinear forms. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 -- June 3, 2022, Proceedings, Part III, volume 13277 of Lecture Notes in Computer Science, pages 582--612. Springer, 2022.
[50]
Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33--44, 2017.
Index Terms
- On the Algebraic Proof Complexity of Tensor Isomorphism
Recommendations
(Semi)Algebraic proofs over {±1} variables
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingOne of the major open problems in proof complexity is to prove lower bounds on AC 0[p]-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus ...
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System
We introduce a new and natural algebraic proof system, whose complexity measure is essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit close connections between effective Nullstellensatzë, proof complexity, ...
Algebraic proofs over noncommutative formulas
We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
In-Cooperation
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Dagstuhl, Germany
Publication History
Published: 29 August 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
CCC '23
CCC '23: conference on Proceedings of the 38th Computational Complexity Conference
July 17 - 20, 2023
Warwick, United Kingdom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in