BARC talk by Manon Blanc

Wednesday, February 5, 2025, Manon Blanc, PhD student at École Polytechnique, France, will give a talk on "Robustness in complexity over the reals: describing complexity classes".

Abstract:
Many recent papers have studied how analogue models of computation work. By "analogue", we mean computing over continuous quantities, while digital models work on discrete structures like bits.

It led to a broader use of Ordinary Differential Equations (ODEs) in computability. In this context, the field of implicit complexity has also been widely studied, using computable analysis.

In the presentation, we will first present algebraic characterisations of PTIME and PSPACE over the reals, using "robust" ODEs. Then, we will see that, with the proper notion of robustness, we can prove that the reachability relation of (real) dynamical systems is computable and even have some complexity results. Eventually, we will how we can have PSPACE-completeness results.

Portrait of Manon BlancBio:
Manon has been a PhD student since the 1st of September 2022 at  the École Polytechnique, France, under the supervision of Olivier Bournez (Alco,LIX) and Nathalie Aubrun (GalaC, LISN). She is interested in computability and complexity over the reals, computable analysis, ordinary differential equations and the links between these topics. Before, she was a student at École Normale Supérieure de Paris-Saclay.

https://www.ip-paris.fr/en/news/new-perspective-complexity

Hosts:
Srikanth Srinivasan and Amir Yehudayoff