2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26425 2026-09-05T19:42:59Z ddc:004 open_access

Kronecker Scaling of Tensors with Applications to Arithmetic Circuits and Algorithms Björklund, Andreas Kaski, Petteri Koana, Tomohiro Nederlof, Jesper tensor rank Kronecker powers arithmetic circuits permanent parameterized algorithms We show that sufficiently low tensor rank for the balanced tripartitioning tensor P_d(x,y,z) = ∑_{A,B,C ∈ binom([3d],d):A∪ B∪ C = [3d]} 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. Under the same low-rank assumption, we obtain exponential-time improvements over the state of the art for a wide variety of related counting and decision problems. Our main methodological contribution is 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Björklund and Petteri Kaski and Tomohiro Koana and Jesper Nederlof 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.36 urn:nbn:de:0030-drops-264258 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.36 eng https://creativecommons.org/licenses/by/4.0/legalcode