2026-07-20T01:06:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22690 2026-04-17T05:32:21Z ddc:004 open_access

A High Dimensional Cramer’s Rule Connecting Homogeneous Multilinear Equations to Hyperdeterminants Joux, Antoine Narayanan, Anand Kumar arithmetic circuits tensors determinants hyperdeterminants We present a new algorithm for solving homogeneous multilinear equations, which are high dimensional generalisations of solving homogeneous linear equations. First, we present a linear time reduction from solving generic homogeneous multilinear equations to computing hyperdeterminants, via a high dimensional Cramer’s rule. Hyperdeterminants are generalisations of determinants, associated with tensors of formats generalising square matrices. Second, we devise arithmetic circuits to compute hyperdeterminants of boundary format tensors. Boundary format tensors are those that generalise square matrices in the strictest sense. Consequently, we obtain arithmetic circuits for solving generic homogeneous boundary format multilinear equations. The complexity as a function of the input dimension varies across boundary format families, ranging from quasi-polynomial to sub exponential. Curiously, the quasi-polynomial complexity arises for families of increasing dimension, including the family of multipartite quantum systems made of d qubits and one qudit. Finally, we identify potential directions to resolve the hardness the hyperdeterminants, notably modulo prime numbers through the cryptographically significant tensor isomorphism complexity class. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Joux and Anand Kumar Narayanan 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.62 urn:nbn:de:0030-drops-226904 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.62 eng https://creativecommons.org/licenses/by/4.0/legalcode