Decision problems on linear recurrence sequences

Nikhil Balaji
Chennai Mathematical Institute

Chaired by
Dr MEEL, Kuldeep Singh, Sung Kah Kay Assistant Professor, School of Computing

  27 Nov 2018 Tuesday, 03:00 PM to 05:00 PM

 COM1-B-03 Active Learning Lab

Given a linear recurrence sequence (LRS) with initial conditions defining an infinite sequence, the \emph{Skolem problem} asks if zero ever occurs in this sequence. Decidability of this problem has been open for several decades. Currently it is known to be decidable for LRS of order up to 4. The best complexity lower bound known is NP-hardness from a 2003 paper of Blondel and Portier. A recent work due to Ouaknine and Worrell shows that decidability of certain related problems on LRS would solve longstanding open problems in Diophantine approximation.

In this talk, I'll give a different proof of the NP-hardness lower bound, which is arguably simpler and yields a subclass of LRS for which the Skolem problem is NP-complete. I'll also mention a few open problems closely related to the Skolem problem.

Along the way, we see how this simple problem relates to verification of probabilistic systems and program termination and highlight a few related questions.

Partly based on joint work with S. Akshay and Nikhil Vyas

Nikhil Balaji obtained his PhD from the Chennai Mathematical Institute advised by Prof. Samir Datta. After a postdoc stint at the CSE department at IITB, he is currently a postdoc at Ulm university in Germany. His research interests include complexity theory -- primarily algebraic/numerical problems and automata theory and verification.