---

I am a CNRS researcher at the Centre de Recherche en Informatique de Lens (CRIL). I have done a PhD at the Institute of Mathematics at the University of Paderborn under the supervision of Peter Bürgisser. I have also spent two years a a postdoc at the Laboratoire d'Informatique de l'École Polytechnique (LIX).

Here is a short CV.

The electronic version of my thesis can be found here.

Contact

CRIL-CNRS/Université d'Artois
Faculté des Sciences Jean Perrin
rue Jean Souvraz, S.P. 18
F-62307 LENS Cedex
FRANCE

Email: mengel@cril.fr

Research interest

The focus of my work lies in the intersection of computational complexity theory, algorithms and combinatorics. In particular, I am very interested in applications in database theory and artificial intelligence. I also used to work in arithmetic circuit complexity.

Publications

• S. Bova, F. Capelli, S. Mengel, F. Slivovsky
  On Compiling CNFs into Structured Deterministic DNNFs
  18th International Conference on Theory and Applications of Satisfiability Testing (SAT 2015)
  Abstract
• H. Chen, S. Mengel
  The Logic of Counting Query Answers: A Study via Existential Positive Queries
  arXiv 1501.07195
  Abstract pdf
• S. Bova, F. Capelli, S. Mengel, F. Slivovsky
  A Strongly Exponential Separation of DNNFs from CNFs
  arXiv 1411.1995
  Abstract pdf
• H. Chen, S. Mengel
  A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
  Proceedings 18th International Conference on Database Theory (ICDT 2015)
  arXiv 1408.0890
  Abstract conference version pdf
• J. Brault-Baron, F. Capelli, S. Mengel
  Understanding model counting for β-acyclic CNF-formulas
  Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015)
  arXiv 1405.6043
  Abstract pdf conference version
• F. Capelli, A. Durand, S. Mengel
  Hypergraph Acyclicity and Propositional Model Counting
  Proceedings 17th International Conference on Theory and Applications of Satisfiability Testing (SAT 2014)
  arXiv 1401.6307
  Abstract conference version
• S. Mengel
  Arithmetic Branching Programs with Memory
  Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2013
  arXiv 1303.1969
  Abstract pdf conference version
• F. Capelli, A. Durand, S. Mengel
  The arithmetic complexity of tensor contractions
  Proceedings Symposium on Theoretical Aspects of Computer Science (STACS) 2013
  invited to the STACS'13 special issue of Theory of Computing Systems
  arXiv 1209.4865
  Abstract conference version
• A. Durand, S. Mengel
  Structural Tractability of Counting of Solutions to Conjunctive Queries
  full version to appear in the ICDT'13 special issue of Theory of Computing Systems
  conference version appeared in Proceeding of the 16th International Conference on Database Theory (ICDT 2013)
  arXiv 1303.2059
  Abstract pdf conference version journal version
• A. Durand, S. Mengel
  The Complexity of Weighted Counting for Acyclic Conjunctive Queries
  Journal of Computer and System Sciences (JCSS) 80(1): 277-296 (2014)
  arXiv 1110.4201
  Abstract pdf
• H. Fournier, G. Malod, S. Mengel
  Monomials in arithmetic circuits: Complete problems in the counting hierarchy
  Proceedings Symposium on Theoretical Aspects of Computer Science (STACS) 2012
  full journal version in computational complexity
  arXiv 1110.6271
  Abstract pdf conference version
• S. Mengel
  Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
  Extended abstract in Proc. of ICALP 2011
  Lecture Notes in Computer Science, Volume 6755/2011, p. 700-711, Springer, 2011
  Abstract pdf Full version
• J. Harant and S. Senitsch
  A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs
  Discrete Mathematics (DM) 09(15):4949-4951 (2009).
  Abstract