Invited Talk by Dr. Nikhil Balaji on Decision problems on linear recurrence sequences

Title: Decision problems on linear recurrence sequences
Speaker: Dr. Nikhil Balaji, Ulm university, Germany.
Host Faculty: Dr. Karteek Sreenivasaiah
Room No: LH-1, academic block A.
Time: 12:00 - 13:00
Abstract:

Given a linear recurrence sequence (LRS) with initial conditions defining an infinite sequence, the Skolem problem asks if zero ever occurs in this sequence? Decidability of the Skolem 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 long standing 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)

Speaker Bio:

Dr. 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.

Dates: Thursday, August 23, 2018 - 12:00 to 13:00