Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912316165980160 |
|---|---|
| author | Björklund, Andreas Kaski, Petteri Koana, Tomohiro Nederlof, Jesper |
| author_facet | Björklund, Andreas Kaski, Petteri Koana, Tomohiro Nederlof, Jesper |
| contents | We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_d(x,y,z)=\sum_{A,B,C\in\binom{[3d]}{d}:A\cup B\cup C=[3d]}x_Ay_Bz_C$ for a large enough constant $d$ implies uniform arithmetic circuits for the matrix permanent that are exponentially smaller than circuits obtainable from Ryser's formula.
We show that the same low-rank assumption implies exponential time improvements over the state of the art for a wide variety of other related counting and decision problems.
As our main methodological contribution, we show that the tensors $P_n$ have a desirable Kronecker scaling property: They can be decomposed efficiently into a small sum of restrictions of Kronecker powers of $P_d$ for constant $d$. We prove this with a new technique relying on Steinitz's lemma, which we hence call Steinitz balancing.
As a consequence of our methods, we show that the mentioned low rank assumption (and hence the improved algorithms) is implied by Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)], a bold conjecture that has recently seen intriguing progress. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05772 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Kronecker scaling of tensors with applications to arithmetic circuits and algorithms Björklund, Andreas Kaski, Petteri Koana, Tomohiro Nederlof, Jesper Data Structures and Algorithms Computational Complexity We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_d(x,y,z)=\sum_{A,B,C\in\binom{[3d]}{d}:A\cup B\cup C=[3d]}x_Ay_Bz_C$ for a large enough constant $d$ implies uniform arithmetic circuits for the matrix permanent that are exponentially smaller than circuits obtainable from Ryser's formula. We show that the same low-rank assumption implies exponential time improvements over the state of the art for a wide variety of other related counting and decision problems. As our main methodological contribution, we show that the tensors $P_n$ have a desirable Kronecker scaling property: They can be decomposed efficiently into a small sum of restrictions of Kronecker powers of $P_d$ for constant $d$. We prove this with a new technique relying on Steinitz's lemma, which we hence call Steinitz balancing. As a consequence of our methods, we show that the mentioned low rank assumption (and hence the improved algorithms) is implied by Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)], a bold conjecture that has recently seen intriguing progress. |
| title | Kronecker scaling of tensors with applications to arithmetic circuits and algorithms |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2504.05772 |