Stefan Mengel
I am a CNRS researcher at the Centre de Recherche en Informatique de Lens (CRIL).
I have defended my habilitation in computer science at Université d’Artois in December 2021, see here for my habilitation thesis. Before joining CNRS, I have spent two years as a postdoc at the Laboratoire d’Informatique de l’École Polytechnique (LIX). In 2013, I have defended a PhD at the Institute of Mathematics at the University of Paderborn under the supervision of Peter Bürgisser. The electronic version of my thesis can be found here.
Here is a short CV.
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
Journals
- Alexis de Colnet, Stefan Mengel
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
J. Artif. Intell. Res., 2023
arxiv journal version
- Stefan Mengel
No Efficient Disjunction or Conjunction of Switch-Lists
J. Satisf. Boolean Model. Comput., 2022
arxiv journal version
- Stefan Mengel, Sebastian Skritek
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection
Theory Comput. Syst., 2021
arxiv journal version
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth
Constant-Delay Enumeration for Nondeterministic Document Spanners
ACM Trans. Database Syst., 2021
arxiv journal version
- Stefan Mengel, Romain Wallon
Graph Width Measures for CNF-Encodings with Auxiliary Variables
J. Artif. Intell. Res., 2020
arxiv journal version
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth
Constant-Delay Enumeration for Nondeterministic Document Spanners
SIGMOD Rec., 2020
arxiv journal version
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
Minimal Distance of Propositional Models
Theory Comput. Syst., 2019
arxiv journal version
- Stefan Mengel
Lower bounds on the mim-width of some graph classes
Discrete Applied Mathematics, 2018
arxiv journal version
- Christian Ikenmeyer, Stefan Mengel
On the relative power of reduction notions in arithmetic circuit complexity
Inf. Process. Lett., 2018
arxiv journal version
- Florent Capelli, Arnaud Durand, Stefan Mengel
The Arithmetic Complexity of Tensor Contraction
Theory Comput. Syst., 2016
arxiv journal version
- Herv{'{e}} Fournier, Guillaume Malod, Stefan Mengel
Monomials in Arithmetic Circuits: Complete Problems in the Counting Hierarchy
Computational Complexity, 2015
arxiv journal version
- Arnaud Durand, Stefan Mengel
Structural Tractability of Counting of Solutions to Conjunctive Queries
Theory Comput. Syst., 2015
arxiv journal version
- Arnaud Durand, Stefan Mengel
The complexity of weighted counting for acyclic conjunctive queries
J. Comput. Syst. Sci., 2014
arxiv journal version
- Jochen Harant, Stefan Senitsch
A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs
Discrete Mathematics, 2009
journal version
Conferences
- Karl Bringmann, Nofar Carmeli, Stefan Mengel
Tight Fine-Grained Bounds for Direct Access on Join Queries
SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022
arxiv conference version
- Stefan Mengel
Changing Partitions in Rectangle Decision Lists
25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022
conference version
- Alexis de Colnet, Stefan Mengel
Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation
Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022
arxiv conference version
- Alexis de Colnet, Stefan Mengel
A Compilation of Succinctness Results for Arithmetic Circuits
Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021
arxiv conference version
- Alexis de Colnet, Stefan Mengel
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
24th International Conference on Theory and Applications of Satisfiability Testing, SAT 2021, Barcelona, Spain, July 5-9, 2021
arxiv conference version
- Stefan Mengel, Friedrich Slivovsky
Proof Complexity of Symbolic QBF Reasoning
24th International Conference on Theory and Applications of Satisfiability Testing, SAT 2021, Barcelona, Spain, July 5-9, 2021
arxiv conference version
- Daniel Le Berre, Pierre Marquis, Stefan Mengel, Romain Wallon
On Irrelevant Literals in Pseudo-Boolean Constraint Learning
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020
arxiv conference version
- Alexis de Colnet, Stefan Mengel
Lower Bounds for Approximate Knowledge Compilation
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020
arxiv conference version
- Stefan Mengel, Romain Wallon
Revisiting Graph Width Measures for CNF-Encodings
22nd International Conference Theory and Applications of Satisfiability Testing, SAT 2019, Lisbon, Portugal, July 9-12, 2019
arxiv conference version
- Stefan Mengel, Sebastian Skritek
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection
22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal
arxiv conference version
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth
Constant-Delay Enumeration for Nondeterministic Document Spanners
22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal
arxiv conference version
- Florent Capelli, Stefan Mengel
Tractable QBF by Knowledge Compilation
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany
arxiv conference version
- Antoine Amarilli, Pierre Bourhis, Stefan Mengel
Enumeration on Trees under Relabelings
21st International Conference on Database Theory, ICDT 2018
arxiv conference version
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Stefan Mengel
Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
Theory and Applications of Satisfiability Testing - SAT 2016
arxiv conference version
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
As Close as It Gets
WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016
conference version
- 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
- Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer
Give Me Another One!
Algorithms and Computation - 26th International Symposium, ISAAC 2015
conference version
- 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
- 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
- Florent Capelli, Arnaud Durand, Stefan Mengel
Hypergraph Acyclicity and Propositional Model Counting
Theory and Applications of Satisfiability Testing - SAT 2014
arxiv conference version
- Arnaud Durand, Stefan Mengel
Structural tractability of counting of solutions to conjunctive queries
Joint 2013 EDBT/ICDT Conferences, ICDT 2013
arxiv conference version
- Stefan Mengel
Arithmetic Branching Programs with Memory
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013
arxiv conference version
- 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
- 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
- Stefan Mengel
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract)
Automata, Languages and Programming - 38th International Colloquium, ICALP 2011
conference version
Other and Preprints
- Stefan Mengel
A short note on the counting complexity of conjunctive queries
preprint
arxiv
- Stefan Mengel
Conjunctive queries, arithmetic circuits and counting complexity
PhD thesis, Universität Paderborn, 2013
thesis
- Stefan Mengel
Counting, Knowledge Compilation and Applications
habilitation thesis, Université d’Artois, 2021
habilitation thesis