  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 questions and structures in physics, mathematics,
computer science, optimization, and more. Accordingly, it is of high interest
to understand their computational complexity. Recently, B\"urgisser et al. gave
the first polynomial-time algorithms for orbit problems of torus actions, that
is, actions of commutative continuous groups on Euclidean space. In this work,
motivated by theoretical and practical applications, we study the computational
complexity of robust generalizations of these orbit problems, which amount to
approximating the distance of orbits in $\mathbb{C}^n$ up to a factor
$\gamma>1$. In particular, this allows deciding whether two inputs are
approximately in the same orbit or far from being so. On the one hand, we prove
the NP-hardness of this problem for $\gamma = n^{\Omega(1/\log\log n)}$ by
reducing the closest vector problem for lattices to it. On the other hand, we
describe algorithms for solving this problem for an approximation factor
$\gamma = \exp(\mathrm{poly}(n))$. Our algorithms combine tools from invariant
theory and algorithmic lattice theory, and they also provide group elements
witnessing the proximity of the given orbits (in contrast to the algebraic
algorithms of prior work). We prove that they run in polynomial time if and
only if a version of the famous number-theoretic $abc$-conjecture holds --
establishing a new and surprising connection between computational complexity
and number theory.
