2026-07-23T20:56:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27074 2026-07-23T11:36:19Z ddc:004 open_access

Fixed-Parameter Degree Bounds and Complexity of the Orbit Closure Intersection Problem for Tensors Doğan, M. Levent Maar, John Oliveira, Rafael Qiao, Youming computational invariant theory geometric complexity theory orbit closure intersection problem The orbit closure intersection problem for a reductive group action is a geometric relaxation of the orbit equality problem. These problems capture a range of isomorphism, degeneration and identity-testing problems in computational complexity. We study this problem for the tensor action of G = SL_n(𝕂) x SL_n(𝕂) x SL_m(𝕂) on 𝒱 = 𝕂ⁿ⊗𝕂ⁿ⊗𝕂^m (equivalently, on m-tuples of n× n-matrices) where the base field is algebraically closed with characteristic zero. We focus on the fixed-parameter regime where m is constant and n is allowed to grow. The case of m = 3 is already interesting in the context of tensor rank and matrix multiplication. Prior to our work, only a special case of this problem, namely when one of the input tensors is the zero-tensor (this corresponds to the null cone problem for the tensor action), was known to be solvable in polynomial time (Bürgisser-Franks-Garg-Oliveira-Walter-Wigderson, FOCS'19). Our main result is to show that the orbit closure intersection problem for the above action can be solved in randomized polynomial time. This is achieved by the following new ingredients: 1) We prove an explicit fixed-parameter bound on the degrees needed to generate the invariant ring for the tensor action: for every fixed m, these bounds are polynomial in n. 2) We prove that there is a succinct encoding of the invariants: we construct a uniform, polynomial-sized arithmetic circuit generating all invariants up to the required degree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik M. Levent Doğan and John Maar and Rafael Oliveira and Youming Qiao 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.32 urn:nbn:de:0030-drops-270741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode