Logo du laboratoire LACL Logo du groupe de recXSherche en informatique mathématique

Florent Madelaine

Research


Home

Research

Teaching

Bio

Etc
My publications
also available on various databases :
arXiv.org
DBLP icon DBLP
HAL icon HAL
ORCID iD icon

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.

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

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 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.
  • 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.