Stefan Mengel
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 as 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.
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
- Stefan Mengel
Lower bounds on the mim-width of some graph classes
Discrete Applied Mathematics, 2018
arxiv journal version bib
- Christian Ikenmeyer, Stefan Mengel
On the relative power of reduction notions in arithmetic circuit complexity
Inf. Process. Lett., 2018
arxiv journal version bib
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel
Enumeration on Trees under Relabelings
21st International Conference on Database Theory, ICDT 2018
arxiv conference version bib
- Daniel Le Berre, Pierre Marquis, Stefan Mengel, Romain Wallon
Pseudo-Boolean Constraints from a Knowledge Representation Perspective
The Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018
conference version bib
- Michael Lampis, Stefan Mengel, Valia Mitsou
QBF as an Alternative to Courcelle’s Theorem
Theory and Applications of Satisfiability Testing - SAT 2018
arxiv conference version bib
- Florent Capelli, Stefan Mengel
Knowledge Compilation, Width and Quantification
preprint
arxiv bib
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth
Constant-Delay Enumeration for Nondeterministic Document Spanners
preprint
arxiv bib
- Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel
A Circuit-Based Approach to Efficient Enumeration
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
arxiv conference version bib
- Hubie Chen, Stefan Mengel
The logic of counting query answers
32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017
arxiv conference version bib
- Stefan Mengel, Sebastian Skritek
On tractable query evaluation for SPARQL
preprint
arxiv bib
accepted for ICDT 2019
- Florent Capelli, Arnaud Durand, Stefan Mengel
The Arithmetic Complexity of Tensor Contraction
Theory Comput. Syst., 2016
arxiv journal version bib
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
The Next Whisky Bar
Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016
conference version bib
- Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky
Knowledge Compilation Meets Communication Complexity
The Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016
conference version bib
- Hubie Chen, Stefan Mengel
Counting Answers to Existential Positive Queries: A Complexity Classification
35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016
arxiv conference version bib
- Stefan Mengel
Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
Theory and Applications of Satisfiability Testing - SAT 2016
arxiv conference version bib
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
As Close as It Gets
WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016
conference version bib
- Herv{'{e}} Fournier, Guillaume Malod, Stefan Mengel
Monomials in Arithmetic Circuits: Complete Problems in the Counting Hierarchy
Computational Complexity, 2015
arxiv journal version bib
- Arnaud Durand, Stefan Mengel
Structural Tractability of Counting of Solutions to Conjunctive Queries
Theory Comput. Syst., 2015
arxiv journal version bib
- Hubie Chen, Stefan Mengel
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
18th International Conference on Database Theory, ICDT 2015
arxiv conference version bib
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
Give Me Another One!
Algorithms and Computation - 26th International Symposium, ISAAC 2015
conference version bib
- Simone Bova, Florent Capelli, Stefan Mengel, Friedrich Slivovsky
On Compiling CNFs into Structured Deterministic DNNFs
Theory and Applications of Satisfiability Testing - SAT 2015
conference version bib
- Johann Brault-Baron, Florent Capelli, Stefan Mengel
Understanding Model Counting for beta-acyclic CNF-formulas
32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
arxiv conference version bib
- Arnaud Durand, Stefan Mengel
The complexity of weighted counting for acyclic conjunctive queries
J. Comput. Syst. Sci., 2014
arxiv journal version bib
- Florent Capelli, Arnaud Durand, Stefan Mengel
Hypergraph Acyclicity and Propositional Model Counting
Theory and Applications of Satisfiability Testing - SAT 2014
arxiv conference version bib
- Stefan Mengel
Conjunctive queries, arithmetic circuits and counting complexity
PhD thesis, Universität Paderborn, 2013
thesis bib
- Arnaud Durand, Stefan Mengel
Structural tractability of counting of solutions to conjunctive queries
Joint 2013 EDBT/ICDT Conferences, ICDT 2013
arxiv conference version bib
- Stefan Mengel
Arithmetic Branching Programs with Memory
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013
arxiv conference version bib
- Florent Capelli, Arnaud Durand, Stefan Mengel
The arithmetic complexity of tensor contractions
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013
arxiv conference version bib
- Hervé Fournier, Guillaume Malod, Stefan Mengel
Monomials in arithmetic circuits: Complete problems in the counting hierarchy
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
arxiv conference version bib
- Stefan Mengel
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract)
Automata, Languages and Programming - 38th International Colloquium, ICALP 2011
conference version bib
- Jochen Harant, Stefan Senitsch
A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs
Discrete Mathematics, 2009
journal version bib