8 citations · 59 across the 30 of their papers we have counts for
13 papers · 1 filter
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
Hubie Chen
The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not t…
Best-case and Worst-case Sparsifiability of Boolean CSPs
Hubie Chen, Bart M. P. Jansen, Astrid Pieterse
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…
Homomorphisms are indeed a good basis for counting: Three fixed-template dichotomy theorems, for the price of one
Hubie Chen
Many natural combinatorial quantities can be expressed by counting the number of homomorphisms to a fixed relational structure. For example, the number of 3-colorings of an undirec…
Asking the metaquestions in constraint tractability
Hubie Chen, Benoit Larose
The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variab…
The parameterized space complexity of embedding along a path
Hubie Chen, Moritz Müller
The embedding problem is to decide, given an ordered pair of structures, whether or not there is an injective homomorphism from the first structure to the second. We study this pro…
Parameter Compilation
Hubie Chen
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…
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
Hubie Chen
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 fram…
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
Hubie Chen, Stefan Mengel
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 probl…
One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries
Hubie Chen, Moritz Müller
We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of s…
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
Hubie Chen, Moritz Müller
We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive q…
Existentially Restricted Quantified Constraint Satisfaction
Hubie Chen
The quantified constraint satisfaction problem (QCSP) is a powerful framework for modelling computational problems. The general intractability of the QCSP has motivated the pursuit…
Beyond Hypertree Width: Decomposition Methods Without Decompositions
Hubie Chen, Victor Dalmau
The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of…