Florent Capelli

Junior Professor

Université d'Artois

CRIL

lastname AT cril.fr

Presentation

Research Interests

My main research interests focus on knowledge compilation, databases theory, graph theory and complexity theory. I am interested in using knowledge compilation to unify and re-explain existing tractability results and discover how hard problems, such as counting problems or enumeration, can be solved on structured instances. For example, my thesis has focused on using knowledge compilation to transform structured CNF formulas into data structures allowing for model counting, hence recovering in a unifying framework every existing algorithm for solving the #SAT problem.

Bio

Since September 2023, I hold a Junior Professor Chair (Chaire de professeur junior) at the University of Artois, working at the CRIL laboratory. Before that, I was an assistant professor (Maître de Conférences) at University of Lille in the LINKS team and have been a postdoctoral fellow at Birkbeck College, working with Igor Razgon. I prepared and defended my PhD thesis Structural restrictions of CNF-formulas: applications to model counting and knowledge compilation under the supervision of Arnaud Durand at Paris Diderot University, which is now part of Université Paris-Cité.

Research Projects

Students

I am lucky to serve or to have served as a PhD advisor of:

Publications

Here is a (most probably outdated) list of my publications. DBLP often does a better job than myself at keeping track of my publication record! I try to add a free and long version of every paper listed below on arXiv. If something is missing, do not hesitate to contact me and ask! You may find some paper on arXiv that I have not added in the list. The reason is often that it corresponds to an old version of some better paper.

Journals

Tractable Circuits in Database Theory
with
Antoine Amarilli
ACM SIGMOD Record
2024
arxiv
doi
Linear Programs with Conjunctive Database Queries
with
Nicolas Crosetti
Joachim Niehren
Jan Ramon
Logical Methods in Computer Science (LMCS)
2024
arxiv
doi
Enumerating models of DNF faster: breaking the dependency on the formula size
with
Yann Strozecki
Discrete Applied Mathematics (DAM)
2021
arxiv
doi
Connecting Knowledge Compilation Classes and Width Parameters
with
Antoine Amarilli
Mikaël Monet
Pierre Senellart
Theory of Computing Systems
2020
arxiv
doi
Counting Minimal Transversals of β-Acyclic Hypergraphs
with
Benjamin Bergougnoux
Mamadou Kanté
Journal of Computer and System Sciences (JCSS)
2019
arxiv
doi
Incremental delay enumeration: Space and time
with
Yann Strozecki
Discrete Applied Mathematics (DAM)
2018
arxiv
doi
The Complexity of Tensor Contraction
with
Arnaud Durand
Stefan Mengel
Theory of Computing Systems
2015
arxiv
doi

Conferences

Dynamic direct access of MSO query evaluation over strings
with
Pierre Bourhis
Stefan Mengel
Cristian Riveros
To appear at ICDT 25
2025
arxiv
A Simple Algorithm for Worst-Case Optimal Join and Sampling
with
Oliver Irwin
Sylvain Salvati
To appear at ICDT 25
2025
arxiv
Direct Access for Conjunctive Queries with Negation
with
Oliver Irwin
ICDT
Best Newcomer Paper
2024
arxiv
doi
Ranked Enumeration for MSO on Trees via Knowledge Compilation
with
Antoine Amarilli
Pierre Bourhis
Mikaël Monet
ICDT
2024
arxiv
doi
A Top-Down Tree Model Counter for Quantified Boolean Formulas
with
Jean-Marie Lagniez
Andreas Plank
Martina Seidl
IJCAI
2024
doi
Geometric Amortization of Enumeration Algorithms
with
Yann Strozecki
STACS
2023
arxiv
doi
Linear Programs with Conjunctive Queries
with
Nicolas Crosetti
Joachim Niehren
Jan Ramon
ICDT
Best Newcomer Paper
2022
arxiv
doi
Certifying Top-Down Decision DNNF Compilers
with
Jean-Marie Lagniez
Pierre Marquis
Thirty-Fifth AAAI Conference on Artificial Intelligence
2021
doi
Tractable QBF by Knowledge Compilation
with
Stefan Mengel
36th Symposium on Theoretical Aspects of Computer Science (STACS)
2019
arxiv
doi
Knowledge compilation languages as proof systems
Theory and Applications of Satisfiability Testing (SAT)
2019
arxiv
doi
Understanding the complexity of #SAT using knowledge compilation
Symposium on Logic in Computer Science (LICS)
2017
arxiv
doi
Knowledge Compilation Meets Communication Complexity
with
Simone Bova
Stefan Mengel
Friedrich Slivovsky
International Joint Conference on Artificial Intelligence (IJCAI)
2016
doi
pdf
Understanding model counting for β-acyclic CNF-formulas
with
Johann Brault-Baron
Stefan Mengel
32th Symposium on Theoretical Aspects of Computer Science (STACS)
2015
arxiv
doi
On Compiling CNFs into Structured Deterministic DNNF
with
Simone Bova
Stefan Mengel
Friedrich Slivovsky
Theory and Applications of Satisfiability Testing (SAT)
2015
doi
pdf
Hypergraph Acyclicity and Propositional Model Counting
with
Arnaud Durand
Stefan Mengel
Theory and Applications of Satisfiability Testing (SAT)
2014
arxiv
doi
The Complexity of Tensor Contraction
with
Arnaud Durand
Stefan Mengel
30th Symposium on Theoretical Aspects of Computer Science (STACS)
2013
arxiv
doi

Preprint

A Knowledge Compilation Take on Binary Polynomial Optimization
with
Silvia Di Gregorio
Alberto Del Pia
Submitted at IPCO 24
2023
arxiv
Non-FPT lower bounds for structural restrictions of decision DNNF
with
Andrea Calì
Igor Razgon
2017
arxiv

Manuscripts

Structural restriction of CNF-formulas: application to model counting and knowledge compilation
Thèse de Doctorat
2016
pdf

Posters

Certifying Top-Down Decision DNNF Compilers
with
Jean-Marie Lagniez
Pierre Marquis
Thirty-Fifth AAAI Conference on Artificial Intelligence
2021
pdf
Compilation des formules CNF
Journées Nationales du GDR IM 2016
2016
pdf

Talks

You can find material on the recent talks I gave or will be given (show older talks).

A simple algorithm for worst case optimal join and sampling
DATA Lab Northeastern Seminar
2025-04-11
slides (html)
slides (pdf)
Dynamic direct access of MSO query evaluation over strings
ICDT 2025
2025-03-25
slides (html)
slides (pdf)
Direct Access for Conjunctive Queries with Negations
Seminaire KRDB
2025-01-23
slides (html)
slides (pdf)
A New Hypergraph Measure for #SAT
Dagstuhl Seminar 24421
2024-10-17
slides (html)
slides (pdf)
A Knowledge Compilation Take on Binary Polynomial Optimization
Séminaire du LIPN
2024-09-12
slides (html)
slides (pdf)
Direct Access for Conjunctive Queries with Negations
Séminaire du DAVID
2024-06-13
slides (html)
slides (pdf)
Direct Access for Conjunctive Queries with Negations
Séminaire Automates, IRIF
2024-04-19
slides (html)
slides (pdf)
From Queries to Circuits
Dagtsuhl Seminar 24032 on Representation, Provenance, and Explanations in Database Theory and Logic
2024-01-17
slides
A Knowledge Compilation Take on Binary Polynomial Optimization
Seminar of Industrial & Systems Engineering department, Wisconsin-Madison University
2023-10-27
slides
Direct Access for Conjunctive Queries with Negation
Workshop Probabilistic Circuits and Logic, Simons Institute
2023-10-18
slides (HTML)
slides (PDF)
A (biased) introduction to Knowledge Compilation
Conférence de rentrée de l'ENS Saclay
2023-10-06
slides
A simpler FPRAS for #NFA
Séminaire de l'équipe LINKS
2023-06-23
slides
Geometric Amortization of Enumeration Algorithms
Symposium on Theoretical Aspects of Computer Science
2023-03-09
Geometric Amortization of Enumeration Algorithms
Fifth Workshop on Enumeration Problems and Applications, WEPA 2022
2022-11-24
slides
accessible version
Certifying Knowledge Compilers and #SAT Solvers
Séminaire de l'équipe RATIO
2021-05-10

Teaching