Florent Madelaine






My publications
also available on various databases :
HAL icon HAL
ORCID iD icon


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.

My papers are available in pdf and other format from here. The recent ones can be found on Arxiv.


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 Antoine Mottet and Manuel Bodirsky.
    arXiv ]

    A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP. LICS 2018.
  • QCSP With Catarina Carvalho and Barnaby Martin.
    ArXiv | doi  ]

    From complexity to algebra and back: Digraph classes, collapsibility, and the PGP. LICS 2015.
  • 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.
    doi | .pdf  ]

    On the containment of forbidden patterns problems. CP 2010, lncs vol 6308, 2010.
    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.