BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1284
DTSTAMP:20230914T125957Z
SUMMARY:On Robustness for Linear Recurrence Sequences
DESCRIPTION:Speaker: Mihir Vahanwala (MPI-SWS\, Saarbrücken)\n\nAbstract:
\nThe Skolem\, Positivity\, and Ultimate Positivity problems for Linear Re
currence Sequences (LRS) are number-theoretic problems whose decidability
has been open for decades. They are known to be at least as hard as Diopha
ntine approximation\, an open number-theoretic problem. LRS have scientifi
c applications ranging from theoretical biology to software verification a
nd formal languages. Given the inherent imprecision and need for safety ma
rgins in the real world\, we consider the problems for LRS with the follow
ing notion of robustness: does the sequence satisfy the required property
despite small perturbations in the given initialisation? Although some int
erpretations of this notion yield problems that are still Diophantine hard
\, others can be shown to be decidable\, in PSPACE even! In this talk\, we
discuss how the decision procedure strings together remarkable and profou
nd results from computational algebra\, number theory\, and logic. The tec
hniques we discuss are indeed a thematic feature of modern progress in thi
s area\, and we briefly sketch how they have been extended to handle more
sophisticated semi-algebraic reachability sets\, and to tackle the problem
of invariant synthesis.\nBio: Mihir Vahanwala is a doctoral researcher a
t MPI-SWS\, Saarbrücken. He works in the Foundations of Algorithmic Verif
ication group led by Joël Ouaknine.\n
URL:https://www.tcs.tifr.res.in/web/events/1284
DTSTART;TZID=Asia/Kolkata:20230405T160000
DTEND;TZID=Asia/Kolkata:20230405T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR