Document

**Published in:** LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

A central computational task in database theory, finite model theory, and computer science at large is the evaluation of a first-order sentence on a finite structure. In the context of this task, the width of a sentence, defined as the maximum number of free variables over all subformulas, has been established as a crucial measure, where minimizing width of a sentence (while retaining logical equivalence) is considered highly desirable. An undecidability result rules out the possibility of an algorithm that, given a first-order sentence, returns a logically equivalent sentence of minimum width; this result motivates the study of width minimization via syntactic rewriting rules, which is this article’s focus. For a number of common rewriting rules (which are known to preserve logical equivalence), including rules that allow for the movement of quantifiers, we present an algorithm that, given a positive first-order sentence ϕ, outputs the minimum-width sentence obtainable from ϕ via application of these rules. We thus obtain a complete algorithmic understanding of width minimization up to the studied rules; this result is the first one - of which we are aware - that establishes this type of understanding in such a general setting. Our result builds on the theory of term rewriting and establishes an interface among this theory, query evaluation, and structural decomposition theory.

Hubie Chen and Stefan Mengel. Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICDT.2024.16, author = {Chen, Hubie and Mengel, Stefan}, title = {{Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.16}, URN = {urn:nbn:de:0030-drops-197984}, doi = {10.4230/LIPIcs.ICDT.2024.16}, annote = {Keywords: width, query rewriting, structural decomposition, term rewriting} }

Document

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

We investigate the List H-Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v ∈ V(G) is mapped to a vertex on its list L(v) ⊆ V(H). An important result by Feder, Hell, and Huang [JGT 2003] states that List H-Coloring is polynomial-time solvable if H is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n-vertex instance be efficiently reduced to an equivalent instance of bitsize 𝒪(n^(2-ε)) for some ε > 0? We prove that if H is not a bi-arc graph, then List H-Coloring does not admit such a sparsification algorithm unless NP ⊆ coNP/poly. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi-arc graphs.

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski. Sparsification Lower Bounds for List H-Coloring. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.58, author = {Chen, Hubie and Jansen, Bart M. P. and Okrasa, Karolina and Pieterse, Astrid and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Sparsification Lower Bounds for List H-Coloring}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {58:1--58:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.58}, URN = {urn:nbn:de:0030-drops-134027}, doi = {10.4230/LIPIcs.ISAAC.2020.58}, annote = {Keywords: List H-Coloring, Sparsification, Constraint Satisfaction Problem} }

Document

**Published in:** LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O(n) constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.

Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-Case and Worst-Case Sparsifiability of Boolean CSPs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.IPEC.2018.15, author = {Chen, Hubie and Jansen, Bart M. P. and Pieterse, Astrid}, title = {{Best-Case and Worst-Case Sparsifiability of Boolean CSPs}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.15}, URN = {urn:nbn:de:0030-drops-102169}, doi = {10.4230/LIPIcs.IPEC.2018.15}, annote = {Keywords: constraint satisfaction problems, kernelization, sparsification, lower bounds} }

Document

**Published in:** LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

The number of variables used by a first-order query is a fundamental measure which has been studied in numerous contexts, and which is known to be highly relevant to the task of query evaluation. In this article, we study this measure in the context of existential positive queries. Building on previous work, we present a combinatorial quantity defined on existential positive queries; we show that this quantity not only characterizes the minimum number of variables needed to express a given existential positive query by another existential positive query, but also that it characterizes the minimum number of variables needed to express a given existential positive query, over all first-order queries. Put differently and loosely, we show that for any existential positive query, no variables can ever be saved by moving out of existential positive logic to first-order logic. One component of this theorem’s proof is the construction of a winning strategy for a certain Ehrenfeucht-Fraiissé type game.

Simone Bova and Hubie Chen. How Many Variables Are Needed to Express an Existential Positive Query?. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bova_et_al:LIPIcs.ICDT.2017.9, author = {Bova, Simone and Chen, Hubie}, title = {{How Many Variables Are Needed to Express an Existential Positive Query?}}, booktitle = {20th International Conference on Database Theory (ICDT 2017)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-024-8}, ISSN = {1868-8969}, year = {2017}, volume = {68}, editor = {Benedikt, Michael and Orsi, Giorgio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.9}, URN = {urn:nbn:de:0030-drops-70545}, doi = {10.4230/LIPIcs.ICDT.2017.9}, annote = {Keywords: existential positive queries, finite-variable logics, first-order logic, query optimization} }

Document

**Published in:** LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

We contribute to a research program that aims to classify, for each finite structure, the computational complexity of the quantified constraint satisfaction problem on the structure. Employing an established algebraic viewpoint to studying this problem family, whereby this classification program can be phrased as a classification of algebras, we give a complete classification of all finite monoids.

Hubie Chen and Peter Mayr. Quantified Constraint Satisfaction on Monoids. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CSL.2016.15, author = {Chen, Hubie and Mayr, Peter}, title = {{Quantified Constraint Satisfaction on Monoids}}, booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-022-4}, ISSN = {1868-8969}, year = {2016}, volume = {62}, editor = {Talbot, Jean-Marc and Regnier, Laurent}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.15}, URN = {urn:nbn:de:0030-drops-65553}, doi = {10.4230/LIPIcs.CSL.2016.15}, annote = {Keywords: quantified constraint satisfaction, universal algebra, computational complexity} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution.
Our main results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.

Hubie Chen. Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 94:1-94:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen:LIPIcs.ICALP.2016.94, author = {Chen, Hubie}, title = {{Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {94:1--94:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.94}, URN = {urn:nbn:de:0030-drops-62290}, doi = {10.4230/LIPIcs.ICALP.2016.94}, annote = {Keywords: proof complexity, polynomial hierarchy, quantified propositional logic} }

Document

**Published in:** LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

In resolving instances of a computational problem, if multiple instances of interest share a feature in common,it may be fruitful to compile this feature into a format that allows for more efficient resolution, even if the compilation is relatively expensive. In this article, we introduce a formal framework for classifying problems according to their compilability. The basic object in our framework is that of a parameterized problem, which here is a language along with a parameterization—a map which provides, for each instance, a so-called parameter on which compilation may be performed. Our framework is positioned within the paradigm of parameterized complexity, and our notions are relatable to established concepts in the theory of parameterized complexity. Indeed, we view our framework as playing a unifying role, integrating together parameterized complexity and compilability theory.

Hubie Chen. Parameter Compilation. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 127-137, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chen:LIPIcs.IPEC.2015.127, author = {Chen, Hubie}, title = {{Parameter Compilation}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {127--137}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.127}, URN = {urn:nbn:de:0030-drops-55771}, doi = {10.4230/LIPIcs.IPEC.2015.127}, annote = {Keywords: compilation, parameterized complexity} }

Document

**Published in:** LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental problem of counting, given a conjunctive query and a relational database, the number of answers to the query on the database. In particular, we study the complexity of this problem relative to sets of conjunctive queries. We present a trichotomy theorem, which shows essentially that this problem on a set of conjunctive queries is either tractable, equivalent to the parameterized CLIQUE problem, or as hard as the parameterized counting CLIQUE problem; the criteria describing which of these situations occurs is simply stated, in terms of graph-theoretic conditions.

Hubie Chen and Stefan Mengel. A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 110-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICDT.2015.110, author = {Chen, Hubie and Mengel, Stefan}, title = {{A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries}}, booktitle = {18th International Conference on Database Theory (ICDT 2015)}, pages = {110--126}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-79-8}, ISSN = {1868-8969}, year = {2015}, volume = {31}, editor = {Arenas, Marcelo and Ugarte, Mart{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.110}, URN = {urn:nbn:de:0030-drops-49804}, doi = {10.4230/LIPIcs.ICDT.2015.110}, annote = {Keywords: database theory, query answering, conjunctive queries, counting complexity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

We study the complexity of
equivalence and isomorphism on
primitive positive formulas with respect to a given structure.
We study these problems for various fixed structures;
we present generic hardness and complexity class containment
results, and give classification theorems for the case of
two-element (boolean) structures.

Matt Valeriote, Simone Bova, and Hubie Chen. On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{valeriote_et_al:DagSemProc.09441.3, author = {Valeriote, Matt and Bova, Simone and Chen, Hubie}, title = {{On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {1--20}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9441}, editor = {Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.3}, URN = {urn:nbn:de:0030-drops-23690}, doi = {10.4230/DagSemProc.09441.3}, annote = {Keywords: Expression complexity, equivalence, isomorphism, primitive positive formulas} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

The general intractability of the constraint satisfaction problem
has motivated the study of the complexity of restricted cases of this problem.
Thus far, the literature has primarily considered the formulation
of the CSP where constraint relations are given explicitly.
We initiate the systematic study of CSP complexity with
succinctly specified constraint relations.
This is joint work with Hubie Chen.

Hubie Chen and Martin Grohe. Constraint Satisfaction with Succinctly Specified Relations. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.06401.5, author = {Chen, Hubie and Grohe, Martin}, title = {{Constraint Satisfaction with Succinctly Specified Relations}}, booktitle = {Complexity of Constraints}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.5}, URN = {urn:nbn:de:0030-drops-8022}, doi = {10.4230/DagSemProc.06401.5}, annote = {Keywords: Constraint satisfaction, complexity, succinct representations} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail