On the Orbit Closure Containment Problem and Slice Rank of Tensors
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
Abstract
We consider the orbit closure containment problem, which, for a given vector and a group orbit, asks if the vector is contained in the closure of the group orbit. Recently, many algorithmic problems related to orbit closures have proved to be quite useful in giving polynomial time algorithms for special cases of the polynomial identity testing problem and several non-convex optimization problems. Answering a question posed by Wigderson, we show that the algorithmic problem corresponding to the orbit closure containment problem is NP-hard. We show this by establishing a computational equivalence between the solvability of homogeneous quadratic equations and a homogeneous version of the matrix completion problem, while showing that the latter is an instance of the orbit closure containment problem. Secondly, we consider the notion of slice rank of tensors, which was recently introduced by Tao, and has subsequently been used for breakthroughs in several combinatorial problems like capsets, sunflower free sets, tri-colored sum-free sets, and progression-free sets. We show that the corresponding algorithmic problem, which can also be phrased as a problem about union of orbit closures, is also NP-hard, hence answering an open question by Bürgisser, Garg, Oliveira, Walter, and Wigderson. We show this by using a connection between the slice rank and the size of a minimum vertex cover of a hypergraph revealed by Tao and Sawin.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers6
- What is in #P and what is not?Christian Ikenmeyer, Igor PakFOCS 2022 · 10 citations
- Demystifying the border of depth-3 algebraic circuitsPranjal Dutta, Prateek Dwivedi, Nitin SaxenaFOCS 2021 · 6 citations
- Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuitsPranjal Dutta, Nitin SaxenaFOCS 2022 · 2 citations
- Simple Linear Loops: Algebraic Invariants and ApplicationsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton VaronkaPOPL 2025 · 2 citations
- On the orbit closure intersection problems for matrix tuples under conjugation and left-right actionsGábor Ivanyos, Youming QiaoSODA 2023 · 1 citation
Related papers
- Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardnessVladimir Lysikov, Michael WalterFOCS 2025 · 3 citations
- Determination Problems for Orbit Closures and Matrix GroupsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton Varonka et al.POPL 2026
- Structure vs. randomness for bilinear mapsAlex Cohen, Guy MoshkovitzSTOC 2021
- Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyondNathaniel Johnston, Benjamin Lovitz, Aravindan VijayaraghavanFOCS 2023 · 5 citations
- Approximately Optimal Core Shapes for Tensor DecompositionsMehrdad Ghadiri, Matthew Fahrbach, Gang Fu, Vahab MirrokniICML 2023 · 14 citations
