Nathanaël Fijalkow
I am a computer scientist working on program synthesis, games, and automata.
program synthesis
games
automata
Get in touch nathanael.fijalkow@gmail.com
Research topics

The conception of computer programs is a complicated, costly, and error-prone task. Program synthesis is an ideal where the program is automatically generated from its specification. I am particularly interested in inductive synthesis, where the specification consists of a set of examples.
Representative work in this topic:
Scaling Neural Program Synthesis with Distribution-based Search. Nathanaël Fijalkow and Guillaume Lagarde and Théo Matricon and Kevin E. Ellis and Pierre Ohlmann and Akarsh Potta. AAAI Conference on Artificial Intelligence, AAAI. 2022

Reactive synthesis is the special case of program synthesis where the program takes actions over time in a partially controllable environment. I focus on temporal synthesis, where the specification is given by a logical formula in linear temporal logic (LTL) and its extensions.
Representative work in this topic:
Assume-Guarantee Synthesis for Prompt Linear Temporal Logic. Nathanaël Fijalkow and Bastien Maubert and Aniello Murano and Moshe Y. Vardi. International Joint Conference on Artificial Intelligence, IJCAI. 2020

Games on graphs is at the intersection of several fields: verification (model-checking games such as parity games), logic and model theory (Ehrenfeucht–Fraïssé games), automata theory (emptiness and acceptance games), reinforcement learning (Markov decision processes), and optimisation (mean payoff and discounted games).
Representative work in this topic:
The Theory of Universal Graphs for Games: Past and Future (invited talk). Nathanaël Fijalkow. Coalgebraic Methods in Computer Science, CMCS. 2020

Markovian models are stochastic models with memoryless dynamics. The distinction with probabilistic automata is that Markovian models such as Markov decision processes are fully observable.
Representative work in this topic:
Controlling a Random Population. Thomas Colcombet and Nathanaël Fijalkow and Pierre Ohlmann. 2021

A dynamical system follows the evolution of a point through repeated applications of a function; the special case of linear dynamical systems is concerned with linear functions, i.e. multiplication by a matrix. Their algorithmic study is deeply intertwined with deep insights from algebraic number theory and geometry. I am particularly interested in invariants for linear dynamical systems, and in related control problems.
Representative work in this topic:
Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem. Nathanaël Fijalkow and Pierre Ohlmann and Joël Ouaknine and Amaury Pouly and James Worrell. 2019

The study of probabilistic automata, in particular algorithms for learning and controlling them, has many applications, including program verification, natural language processing, modelling of biological systems, and machine learning.
Representative work in this topic:
Undecidability results for probabilistic automata. Nathanaël Fijalkow. 2017
News
Course on Monte Carlo Tree Search at the EJCIM School
I will be teaching a course together with Emilie Kaufmann on Monte Carlo Tree Search (the algorithm powering Alpha Go!) at the EJCIM school in June
Dagstuhl seminar
I am co-organising a Dagstuhl seminar on the Futures of Reactive Synthesis to be held in September 2023
MFCS Conference
I am on the Program Committee of the MFCS (Mathematical Foundations of Computer Science) Conference.
Visiting University of Warsaw
I will be visiting the University of Warsaw from September 2022 to June 2023 to work with Wojtek Czerwinski.
TheoretiCS
I am serving as Managing Editor for TheoretiCS.
Talk at the GDR-IA Seminar Series
I'm giving an online talk at the GDR-IA seminar series on May 4 on Neural Program Synthesis
Talk at the IARCS Verification Seminar Series
I'm giving an online talk at the IARCS seminar series on April 5 on Neural Program Synthesis
CSR Conference
I am on the Program Committee of the CSR (Computer Science in Russia) Conference.
Research Blog
Collection of research notes, short introductions to recent papers, classical results, open problems.
Collaboration
I am a junior researcher at CNRS in LaBRI, Bordeaux (chargé de recherche). I am also a research fellow of The Alan Turing Institute of data science and artificial intelligence in London.
I am looking for a two-year postdoc to work on the G4S project: Games for Synthesis. Please contact me for details!