11 Search Results for "Chen, Hubie"

Document
DOI: 10.4230/LIPIcs.ICDT.2024.16
Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity

Authors: Hubie Chen and Stefan Mengel

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

Abstract
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.
Cite as

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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.91
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order

Authors: J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph ̄{H} in any finite field of prime order ℤ_p. The subproblem with graph H was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph ̄{H} collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite (K_{3,3}$1{e}, {domino})-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with p = 2 this establishes new results.
Cite as

J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lagodzinski_et_al:LIPIcs.ICALP.2021.91,
  author =	{Lagodzinski, J. A. Gregor and G\"{o}bel, Andreas and Casel, Katrin and Friedrich, Tobias},
  title =	{{On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{91:1--91:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.91},
  URN =		{urn:nbn:de:0030-drops-141608},
  doi =		{10.4230/LIPIcs.ICALP.2021.91},
  annote =	{Keywords: Algorithms, Theory, Quantum Graphs, Bipartite Graphs, Graph Homomorphisms, Modular Counting, Complexity Dichotomy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.58
Sparsification Lower Bounds for List H-Coloring

Authors: Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.IPEC.2018.15
Best-Case and Worst-Case Sparsifiability of Boolean CSPs

Authors: Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.ICDT.2017.9
How Many Variables Are Needed to Express an Existential Positive Query?

Authors: Simone Bova and Hubie Chen

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.CSL.2016.15
Quantified Constraint Satisfaction on Monoids

Authors: Hubie Chen and Peter Mayr

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.ICALP.2016.94
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

Authors: Hubie Chen

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.IPEC.2015.127
Parameter Compilation

Authors: Hubie Chen

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.ICDT.2015.110
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries

Authors: Hubie Chen and Stefan Mengel

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/DagSemProc.09441.3
On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas

Authors: Matt Valeriote, Simone Bova, and Hubie Chen

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/DagSemProc.06401.5
Constraint Satisfaction with Succinctly Specified Relations

Authors: Hubie Chen and Martin Grohe

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

Abstract
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.
Cite as

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-dev.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}
}
  • Refine by Author
  • 10 Chen, Hubie
  • 2 Bova, Simone
  • 2 Jansen, Bart M. P.
  • 2 Mengel, Stefan
  • 2 Pieterse, Astrid
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Computing methodologies → Symbolic and algebraic algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph coloring
  • Show More...

  • Refine by Keyword
  • 1 Algorithms
  • 1 Bipartite Graphs
  • 1 Complexity Dichotomy
  • 1 Constraint Satisfaction Problem
  • 1 Constraint satisfaction
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 2 2015
  • 2 2016
  • 1 2006
  • 1 2010
  • 1 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact