On the complexity of the Orbit Problem

We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem -- determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NP^RP.

Journal of the ACM 63(3), 2016. 40 pages.
Notable Article, ACM Computing Reviews 21st Annual Best of Computing (2016).

PDF © 2016 ACM.