Affine Subspace Reachability Problems

Speaker: 

Time: 

Friday, 15 November 2019, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

Abstract: Given an $n \times n$  rational matrix A, a vector $u \in \mathbb{Q}^n$ and an affine subspace $W \subset \mathbb{Q}^n$ , the affine subspace reachability problem asks whether there exists $t \in \mathbb{N}$ such that $A^t u \in W$. It is not known whether this problem is decidable or undecidable for the general case.

In this talk, we will look at some decidable cases of this problem. One of the interesting cases is the following:
Given algebraic real numbers $x,y, |x| \leq 1, |y| \leq 1, x = \cos \theta$, does there exist a natural number $t$ such that $y = \cos t \theta$.

This is a part of my master's project which is done under guidance of Piyush from STCS, TIFR, and Akshay from IIT Bombay.