Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

Andreas Björklund; Petteri Kaski; Tomohiro Koana; Jesper Nederlof

paper

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

arXiv:2504.05772

Abstract

We show that sufficiently low tensor rank for the balanced tripartitioning tensor $P_{d} (x, y, z) = \sum_{A, B, C \in (d [ 3 d ]) : A \cup B \cup C = [3 d]} x_{A} y_{B} z_{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.