Journal article

The polytope-collision problem

Abstract:

The Orbit Problem consists of determining, given a matrix $A\in\mathbb{R}^{d\times d}$ and vectors $x,y\in \mathbb{R}^d$, whether there exists $n\in \mathbb{N}$ such that $A^n=y$. This problem was shown to be decidable in a seminal work of Kannan and Lipton in the 1980s. Subsequently, Kannan and Lipton noted that the Orbit Problem becomes considerably harder when the target $y$ is replaced with a subspace of $\mathbb{R}^d$. Recently, it was shown that the problem is decidable for vector-space...

Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Access Document

Files:
• (pdf, 565.2KB)

Authors

More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Leibniz International Proceedings in Informatics Publisher's website
Journal:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) Journal website
Publication date:
2017-07-05
Acceptance date:
2017-04-14
Pubs id:
pubs:658320
URN:
uri:e870c1c8-f10b-4734-bcd6-2511be823a72
UUID:
uuid:e870c1c8-f10b-4734-bcd6-2511be823a72
Local pid:
pubs:658320
Keywords: