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

### Access Document

Files:
• (Version of record, pdf, 565.2KB)

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
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-01
Acceptance date:
2017-04-14
Source identifiers:
658320
Keywords:
Pubs id:
pubs:658320
UUID:
uuid:e870c1c8-f10b-4734-bcd6-2511be823a72
Local pid:
pubs:658320
Deposit date:
2017-05-10