Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
Vladimir Lysikov, Michael Walter
Many natural computational problems in computer science, mathematics, physics, and other sciences amount to deciding if two objects are equivalent. Often this equivalence is define…
cs.CC2024
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Peter Bürgisser, Mahmut Levent DoÄan, Visu Makam +2
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous que…