License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.4
URN: urn:nbn:de:0030-drops-182748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18274/
Galesi, Nicola ;
Grochow, Joshua A. ;
Pitassi, Toniann ;
She, Adrian
On the Algebraic Proof Complexity of Tensor Isomorphism
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.
BibTeX - Entry
@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4,
author = {Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian},
title = {{On the Algebraic Proof Complexity of Tensor Isomorphism}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {4:1--4:40},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18274},
URN = {urn:nbn:de:0030-drops-182748},
doi = {10.4230/LIPIcs.CCC.2023.4},
annote = {Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra}
}
|
Keywords: |
|
Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
