research
∙
04/23/2021
Tractability of Quantified Temporal Constraints To The Max
A temporal constraint language is a set of relations that are first-orde...
share
research
∙
09/17/2020
Sparsification Lower Bounds for List H-Coloring
We investigate the List H-Coloring problem, the generalization of graph ...
research
∙
07/28/2020
Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems
Constraint satisfaction problems (CSPs) are an important formal framewor...
research
∙
05/22/2020
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
The constraint satisfaction problem (CSP) on a finite relational structu...
research
∙
09/17/2018
Best-case and Worst-case Sparsifiability of Boolean CSPs
We continue the investigation of polynomial-time sparsification for NP-c...
research
∙
09/30/2017
Homomorphisms are indeed a good basis for counting: Three fixed-template dichotomy theorems, for the price of one
Many natural combinatorial quantities can be expressed by counting the n...
research
∙
04/04/2016
Asking the metaquestions in constraint tractability
The constraint satisfaction problem (CSP) involves deciding, given a set...
research
∙
05/19/2014
An Algebraic Hardness Criterion for Surjective Constraint Satisfaction
The constraint satisfaction problem (CSP) on a relational structure B is...
research
∙
03/02/2014
Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
We consider the quantified constraint satisfaction problem (QCSP) which ...
research
∙
06/18/2012
On the Complexity of Existential Positive Queries
We systematically investigate the complexity of model checking the exist...
research
∙
04/26/2011