Lune

SODA2023Top-tier venue

On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions

Gábor Ivanyos, Youming Qiao

Abstract

Let G be a linear algebraic group acting on the vector space V . Given v, v ′ ∈ V , the orbit closure intersection problem asks to decide if the orbit closures of v and v ′ under G intersect. Due to connections with polynomial identity testing, the orbit closure intersection problems for the conjugation and left-right actions on matrix tuples received considerable attention in computational complexity and computational invariant theory, as seen in the works of Forbes-Shpilka (RANDOM 2013), Allen-Zhu-Garg-Li-Oliveira-Wigderson (STOC 2018), and Derksen-Makam (Algebra & Number Theory 2020). In this paper, we present new algorithms for the orbit closure problem for the conjugation and left-right actions on matrix tuples. The main novel feature is that in the case of intersecting orbit closures, our algorithm outputs cosets of one-parameter subgroups that drive the matrix tuples to a tuple in the intersection of the orbit closures.

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.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardnessVladimir Lysikov, Michael WalterFOCS 2025 · 3 citations
  2. Canonical Forms for Matrix Tuples in Polynomial TimeYouming Qiao, Xiaorui SunFOCS 2024 · 1 citation

Builds on1

  1. On the Orbit Closure Containment Problem and Slice Rank of TensorsMarkus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey et al.SODA 2021 · 7 citations

Related papers

  1. Determination Problems for Orbit Closures and Matrix GroupsRida Ait El Manssour, George Kenison, Mahsa Shirmohammadi, Anton Varonka et al.POPL 2026
  2. Implementing geometric complexity theory: on the separation of orbit closures via symmetriesChristian Ikenmeyer, Umangathan KandasamySTOC 2020 · 2 citations
  3. Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varietiesVisu Makam, Avi WigdersonFOCS 2020 · 2 citations
  4. Equivalence Test for Read-Once Arithmetic FormulasNikhil Gupta, Chandan Saha, Bhargav ThankeySODA 2023
  5. On the Subspace Orbit Problem and the Simultaneous Skolem ProblemPiotr Bacik, Anton VaronkaLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines