Search Results

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.