Seminar of Algorithms of Saclay Plateau: Manon Blanc on Wednesday 28 June 2023 at 10h00

===== Seminar "Algorithms of Saclay Plateau" =====

Dear all,

For the next seminar of the seminar "Algorithms of Saclay Plateau", we are happy to welcome Manon Blanc.

***** Wednesday 28 June 2023 at 10h00, room Grace Hopper *****

Manon Blanc -- Measuring robustness of dynamical systems. Relating time and space to length and precision

Verification of discrete time or continuous time dynamical systems is known to be undecidable. However, undecidability is known not to hold for robust systems: if robustness is defined as the fact that the reachability relation is stable under infinitesimal perturbation,  then decidability holds. Similarly, while undecidability holds for logical formulas over the reals, it does not when considering $\delta$-undecidability, i.e. when properties are either true or delta-far from being true. We first relate these notions of robustness. Then, we extend these statements at the complexity level: When a system is robust, it makes sense to quantify at which level of perturbation a system is robust. We prove assuming robustness to polynomial perturbation on precision leads to PSPACE and even to a characterization of PSPACE. We prove assuming robustness to polynomial perturbation on time or length leads to similar statements but with PTIME. We also relate this to analogue models of computation.


TBA

The list of next seminars can be found at:
https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar/

The calendar of seminars can be found at:
https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar.ics