2025/04/08 by Björklund, Andreas, Kaski, Petteri, Koana, Tomohiro +1 · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.05772
We show that sufficiently low tensor rank for the balanced tripartitioning tensor Pd(x,y,z)=∑_A,B,C∈\binom[3d]d:A∪ B∪ C=[3d]xAyBzC 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 Pn have a desirable Kronecker scaling property: They can be decomposed efficiently into a small sum of restrictions of Kronecker powers of Pd 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.