Publications and Talks

Also available on DBLP. If you encounter any difficulty locating a PDF, please contact me.

Conference Papers

2025 A (1+ε)-approximation for ultrametric embedding in subquadratic time
with Gabriel Bathie
AAAI [paper] [arXiv] [code]
2025 Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis
with Théo Matricon, Nathanaël Fijalkow
AAAI — Invited for oral presentation [paper]
2022 Scaling Neural Program Synthesis with Distribution-Based Search
with Nathanaël Fijalkow, Théo Matricon, Kevin Ellis, Pierre Ohlmann, Akarsh Nayan Potta
AAAI [paper]
2021 Improving Ultrametrics Embeddings Through Coresets
with Vincent Cohen-Addad, Rémi de Joannis de Verclos
ICML [paper]
2021 The complexity of learning linear temporal formulas from examples
with Nathanaël Fijalkow
ICGI [paper]
2020 Lower Bounds for Arithmetic Circuits via the Hankel Matrix
with Nathanaël Fijalkow, Pierre Ohlmann, Olivier Serre
STACS [paper]
2020 On Efficient Low Distortion Ultrametric Embedding
with Vincent Cohen-Addad, Karthik C. S.
ICML [paper]
2020 Trade-Offs Between Size and Degree in Polynomial Calculus
with Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
ITCS [paper]
2018 Lempel-Ziv: a “one-bit catastrophe” but not a tragedy
with Sylvain Perifel
SODA [paper]
2017 Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees
with Nutan Limaye, Srikanth Srinivasan
MFCS [paper]

2022 DeepSynth: Scaling Neural Program Synthesis with Distribution-based Search
with Théo Matricon, Nathanaël Fijalkow, Kevin Ellis
J. Open Source Softw. [paper]
2021 Lower Bounds for Arithmetic Circuits via the Hankel Matrix
with Nathanaël Fijalkow, Pierre Ohlmann, Olivier Serre
Comput. Complex. [paper]
2020 d-Galvin Families
with Johan Håstad, Joseph Swernofsky
Electron. J. Comb. [paper]
2019 Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
with Nutan Limaye, Srikanth Srinivasan
Comput. Complex. [paper]
2019 Non-commutative computations: lower bounds and polynomial identity testing
with Guillaume Malod, Sylvain Perifel
Chic. J. Theor. Comput. Sci. [paper]
2017 De Bruijn-Erdős-type theorems for graphs and posets
with Pierre Aboulker, David Malec, Abhishek Methuku, Casey Tompkins
Discret. Math. [paper]

2026 Analyzing and Leveraging the k-Sensitivity of LZ77
with Gabriel Bathie, Paul Huber, Akka Zemmari [arXiv]
2025 ParamExplorer: A framework for exploring parameters in generative art
with Julien Gachadoat [arXiv] [code]
2023 Learning temporal formulas from examples is hard
with Corto Mascle, Nathanaël Fijalkow [arXiv]
2018 Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees
with Nathanaël Fijalkow, Pierre Ohlmann [arXiv]

Henri Potier à l’école de la complexité, Le blog binaire, Le Monde
avec Sylvain Perifel
- Chapitre 1
- Chapitre 2
Un seul bit vous manque, et ça ne compresse plus…, INS2I CNRS
La théorie de la complexité algorithmique, Interstices