ANR-24-CE48-7504
Duration: 01/01/2025–31/12/2029 (60 months).
[CALL] Postdoc (Marseille, France)
ANR project ALARICE is proposing a postdoc position at the interface between computational models, discrete dynamical systems (such as cellular automata, automata networks), algorithmic complexity, finite-model theory, graph logics… Candidates with expertise in (at least) two of these fields will be particularly considered.
The hired researcher will join the Natural Computing group at LIS in Marseille Luminy.
Starting date: September 2025 (flexible).
Duration: 1 or 2 years.
Salary: 2600€-3370€ gross per month (2100€-2700€ net), depending on experience.
Application: send a CV and a synthetic description of past/present/future research projects by email to kevin.perrot@lis-lab.fr before June 1st, 2025.
Feel free to ask details about the project or introduce yourself before this deadline.
Notification: mid June 2025.
The candidate should have defended his PhD thesis, or already planned the defense. We welcome all nationalities and genders.
Spirit
One of the most meaningful theorem in computer science is due to Rice, in 1953:
Theorem. Any non-trivial question on the behavior of programs is undecidable.
What is striking about this statement is its generality: it holds for any non-trivial question.
Furthermore, trivial questions are answered by one of two trivial programs
(either returning always “yes”, or returning always “no”),
hence the dichotomy is both sharp and deep.
This brings its interpretation to an epistemological ground regarding the powers and limits
of algorithmic problem solving (i.e., by means of a computer, which is nowadays ubiquitous).
Attaining this level of generality is the guiding principle of our project ALARICE
— to obtain results “à la Rice”.
Rice’s theorem belongs to the field of computability theory, and we aim to bring its spirit to the field of complexity theory, which is another fundamental pillar of computer science. This shift towards the decidable world is motivated by the objects under consideration, finite dynamical systems, where virtually any question is decidable via a naive exhaustive search. As a consequence, the formulation of Rice-like results consists in general (lower and upper) bounds of computational complexity. The discrete dynamical systems at stake are defined by “simple” local rules, and readily show “complex” global behaviors. They are informally referred to as “complex systems”, and we endorse that the computational complexity point of view provides a theoretical framework to formalize this common intuition.
ALARICE is composed of three Objectives.
1) Develop a novel combination of techniques based on
the expressiveness of finite model theory,
which allows to prove metatheorems, provided a correct definition of non-triviality.
2) Adopt a systematic complexity point of view approach on all facets of automata network theory,
aimed at gaining legible knowledge towards the implementation of vaster metatheorem proof techniques.
3) Transfer the results to other models of computation, such as finite cellular automata and reaction systems,
through the reconsideration of simulations in the unifying framework of reductions,
and reach an understanding of the complexity of finite dynamical systems as abstract and broad as possible.
Consortium
Partner 1 (Marseille, coord. LIS):
- Chalopin Jérémie (DR CNRS LIS/DALGO)
- Defrain Oscar (MCF LIS/ACRO)
- Goubault–Larrecq Aliénor (PhD LIS/CANA)
- Guillon Pierre (CR CNRS I2M)
- Monmege Benjamin (MCF LIS/MOVE)
- Ohlmann Pierre (CR CNRS LIS/MOVE)
- Perrot Kévin (MCF LIS/CANA, head)
- Porreca Antonio E. (MCF LIS/CANA)
- Rolland Marius (PhD LIS/CANA)
- Sené Sylvain (PU LIS/CANA)
- Tapin Léah (PhD LIS/CANA)
- Theyssier Guillaume (CR CNRS I2M)
Partner 2 (Nice+, coord. I3S):
- Bridoux Florian (CR CNRS I3S, Nice)
- Durbec Amélia (Postdoc Junia, Lille)
- Gamard Guilhem (MCF Loria, Nancy)
- Richard Adrien (MCF I3S, Nice, head)
- Riva Sara (MCF CRISTAL, Lille)
Institutions
- Agence Nationale de la Recherche
- Centre National de la Recherche Scientifique
- Inria
- Laboratoire d’Informatique et des Systèmes
- Aix Marseille Université
- Laboratoire d’Informatique, Signaux et Systèmes de Sophia Antipolis
- Université Côte d’Azur
- Institut de Mathématiques de Marseille
- JUNIA
- Laboratoire lorrain de Recherche en Informatique et ses Applications
- Centre de Recherche en Informatique, Signal et Automatique de Lille
Events
-
2025-07-30 (1 week)
AUTOMATA-WAN-2025 takes place in Lille, CRIStAL. -
2025-03-27 (3 days)
Congrès MATh.en.JEANS in Marseille, with Pierre Guillon, Kévin Perrot and Marius Rolland (year-long research activities with high school Pierre Mendes France, 13127 Vitrolles, in partnership with maths teacher Jessica Gouirand-Thuillet). -
2025-03-11 (2 days)
ALARICE kickoff meeting at CIRM, Marseille Luminy.
Publications
-
Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Foundations of Block-Parallel Automata Networks.” Preprint, 2025.
arXiv-link
-
Porreca, Antonio E., and Marius Rolland. “Injectivity of Polynomials over Finite Discrete Dynamical Systems.” Preprint, 2025.
arXiv-link
-
Doré, François, Kévin Perrot, Antonio E. Porreca, Sara Riva, and Marius Rolland. “Roots in the Semiring of Finite Deterministic Dynamical Systems.” Preprint, 2025.
arXiv-link
-
2024
Goubault–Larrecq, Aliénor, and Kévin Perrot. “Rice-like Complexity Lower Bounds for Boolean and Uniform Automata Networks.” Preprint, 2024.
arXiv-link
-
2024
Theyssier, Guillaume. “FO Logic on Cellular Automata Orbits Equals MSO Logic.” In Proceedings of ICALP’2024, 297:154:1–154:20. LIPIcs. Schloss Dagstuhl, 2024.
DOI-link
HAL-link
PDF-link
-
2023
Gamard, Guilhem, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier. “Hardness of Monadic Second-Order Formulae over Succinct Graphs.” Preprint, 2023.
HAL-link
arXiv-link
-
2021
Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Rice-like Theorem for Automata Networks.” In Proceedings of STACS’21, 187:32:1–32:17. LIPIcs. Schloss Dagstuhl, 2021.
DOI-link
PDF-link
Credits
Site made with Jekyll
from the template BlackDoc
and jekyll-scholar.
Runs on gitlab.lis-lab.fr/kevin.perrot/alarice
with Gitlab pages.
Something wrong? Bug or obsolete info?
Please email Kevin Perrot at <name dot surname at lis-lab dot fr>
. Thanks!