Florent Madelaine

Topics

I am interested in theoretical aspects of computer science. In particular, I focus my work in the area of finite model theory and (descriptive) complexity theory.

My contributions involves mostly constraint satisfaction problems (CSP) and its quantified extension (QCSP) and I have been collaborating for some time with Barnaby Martin on this topic.

I also work on MMSNP, a logic introduced by Feder and Vardi in the same paper in which they conjectured that CSP follows a dichotomy. It turns out that MMSNP captures problems with infinite domain, and that not only it has a dichotomy but it satisfies an algebraic condition for tractability from a conjecture extending that of the dichotomy theorem for finite domain CSPs. Its extension MMNSP2, studied also as GMSNP is also an infinite CSP. For this class, the dichotomy remains open, though Alexey Barsukov has made some progress on this front.

My papers are available in pdf and other format from here. Most of the recent ones can be found on Arxiv (either as authored by Florent R. Madelaine or by Florent Madelaine).

Affiliations

I am currently a member of LACL and a member of the CNRS national research group GdR IM.

I thought that I was not a number but I am told that I am ORCID iD icon https://orcid.org/0000-0002-8528-7105

Selected Works [full list of publications]

MMSNP With Alexey Barsukov.
[ arXiv ]

On guarded extensions of MMSNP. Logical Methods in Computer Science, 2025. To appear.
QCSP With Catarina Carvalho, Barnaby Martin, and Dmitriy Zhuk.
[ ArXiv | ]

The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Trans. Comput. Log., 24(1):5:1--5:26, 2023.
MMSNP With Antoine Mottet and Manuel Bodirsky.
[ arXiv ]

A proof of the algebraic tractability conjecture for monotone monadic SNP. SIAM J. Comput. 50(4), 2021.
QCSP With Hubie Chen and Barnaby Martin.
[ ArXiv | doi ]

Quantified constraints and containment problems. Logical Methods in Computer Science, 11(3), 2015.
QCSP With Barnaby Martin.
[ ArXiv ]

On the complexity of the model checking problem. SIAM J. Comput. 47(3), 2018.
QCSP with Barnaby Martin.
[ ArXiv | .pdf ]

The complexity of positive first-order logic without equality. ACM Trans. Comput. Log., 13(1):5, 2012.
MMSNP
[ doi | .pdf ]

On the containment of forbidden patterns problems. CP 2010, lncs vol 6308, 2010.
MMSNP
[ ArXiV ]

Universal structures and the logic of forbidden patterns. Logical Methods in Computer Science, 5(2), 2009.
MMSNP With Iain A. Stewart.
[ doi | pdf ]

Constraint satisfaction, logic and forbidden patterns. SIAM J. Comput., 37(1), 2007.
CSP With Tomás Feder and Iain A. Stewart.
[ doi | .ps ]

Dichotomies for classes of homomorphism problems involving unary functions. Theor. Comput. Sci., 314(1-2):1-43, 2004.