Stefan Mengel

Hermann Wilhelm

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Database Theory, 2024

Skyline Operators for Document Spanners.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Database Theory, 2024

2023

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2023

Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability.

[BibT_eX]

[DOI]

CoRR, 2023

Subtractive Mixture Models via Squaring: Representation and Learning.

[BibT_eX]

[DOI]

Lorenzo Loconte

Aleksanteri M. Sladek

CoRR, 2023

Bounds on BDD-Based Bucket Elimination.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing, 2023

2022

No Efficient Disjunction or Conjunction of Switch-Lists.

[BibT_eX]

[DOI]

J. Satisf. Boolean Model. Comput., 2022

Changing Partitions in Rectangle Decision Lists.

[BibT_eX]

[DOI]

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

Tight Fine-Grained Bounds for Direct Access on Join Queries.

[BibT_eX]

[DOI]

Karl Bringmann

Nofar Carmeli

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection.

[BibT_eX]

[DOI]

Sebastian Skritek

Theory Comput. Syst., 2021

A short note on the counting complexity of conjunctive queries.

[BibT_eX]

[DOI]

CoRR, 2021

Proof Complexity of Symbolic QBF Reasoning.

[BibT_eX]

[DOI]

Friedrich Slivovsky

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2021, 2021

A Compilation of Succinctness Results for Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, 2021

Counting, Knowledge Compilation and Applications.

[BibT_eX]

[DOI]

, 2021

2020

Constant-Delay Enumeration for Nondeterministic Document Spanners.

[BibT_eX]

[DOI]

SIGMOD Rec., 2020

Revisiting Graph Width Measures for CNF-Encodings.

[BibT_eX]

[DOI]

Romain Wallon

J. Artif. Intell. Res., 2020

Lower Bounds for Approximate Knowledge Compilation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

On Irrelevant Literals in Pseudo-Boolean Constraint Learning.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

2019

Minimal Distance of Propositional Models.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

Tractable QBF by Knowledge Compilation.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Enumeration on Trees with Tractable Combined Complexity and Efficient Updates.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

2018

On the relative power of reduction notions in arithmetic circuit complexity.

[BibT_eX]

[DOI]

Christian Ikenmeyer

Inf. Process. Lett., 2018

Lower bounds on the mim-width of some graph classes.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Knowledge Compilation, Width and Quantification.

[BibT_eX]

[DOI]

CoRR, 2018

QBF as an Alternative to Courcelle's Theorem.

[BibT_eX]

[DOI]

Michael Lampis

Valia Mitsou

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

Pseudo-Boolean Constraints from a Knowledge Representation Perspective.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Enumeration on Trees under Relabelings.

[BibT_eX]

[DOI]

Antoine Amarilli

Pierre Bourhis

Proceedings of the 21st International Conference on Database Theory, 2018

2017

On tractable query evaluation for SPARQL.

[BibT_eX]

[DOI]

Sebastian Skritek

CoRR, 2017

The logic of counting query answers.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

A Circuit-Based Approach to Efficient Enumeration.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The Arithmetic Complexity of Tensor Contraction.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Lower Bounds on the mim-width of Some Perfect Graph Classes.

[BibT_eX]

[DOI]

CoRR, 2016

As Close as It Gets.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation - 10th International Workshop, 2016

Parameterized Compilation Lower Bounds for Restricted CNF-Formulas.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

Counting Answers to Existential Positive Queries: A Complexity Classification.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Knowledge Compilation Meets Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

The Next Whisky Bar.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Structural Tractability of Counting of Solutions to Conjunctive Queries.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

The Logic of Counting Query Answers: A Study via Existential Positive Queries.

[BibT_eX]

[DOI]

CoRR, 2015

Monomials in Arithmetic Circuits: Complete Problems in the Counting Hierarchy.

[BibT_eX]

[DOI]

Hervé Fournier

Guillaume Malod

Comput. Complex., 2015

Understanding Model Counting for beta-acyclic CNF-formulas.

[BibT_eX]

[DOI]

Johann Brault-Baron

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

On Compiling CNFs into Structured Deterministic DNNFs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2015, 2015

Give Me Another One!

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Database Theory, 2015

2014

The complexity of weighted counting for acyclic conjunctive queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Understanding model counting for $β$-acyclic CNF-formulas.

[BibT_eX]

[DOI]

Johann Brault-Baron

CoRR, 2014

Expander CNFs have Exponential DNNF Size.

[BibT_eX]

[DOI]

CoRR, 2014

Hypergraph Acyclicity and Propositional Model Counting.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

2013

Conjunctive queries, arithmetic circuits and counting complexity.

[BibT_eX]

[DOI]

PhD thesis, 2013

The arithmetic complexity of tensor contractions.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Arithmetic Branching Programs with Memory.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2011

On Polynomials Defined by Acyclic Conjunctive Queries and Weighted Counting Problems

[BibT_eX]

[DOI]

CoRR, 2011

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract).

[BibT_eX]

[DOI]