research
∙
02/07/2023
On the complexity of the approximate hypergraph homomorphism problem
Understanding the computational complexity of fragments of the Constrain...
share
research
∙
02/06/2023
Sparsification of Monotone k-Submodular Functions of Low Curvature
Pioneered by Benczur and Karger for cuts in graphs [STOC'96], sparsifica...
research
∙
01/27/2023
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
General factors are a generalization of matchings. Given a graph G with ...
research
∙
11/06/2022
Approximate Graph Colouring and the Hollow Shadow
We show that approximate graph colouring is not solved by constantly man...
research
∙
10/15/2022
Approximate Graph Colouring and Crystals
We show that approximate graph colouring is not solved by any level of t...
research
∙
10/07/2022
Boolean symmetric vs. functional PCSP dichotomy
Given a 3-uniform hypergraph (V,E) that is promised to admit a {0,1}-col...
research
∙
07/05/2022
Hierarchies of Minion Tests for PCSPs through Tensors
We provide a unified framework to study hierarchies of relaxations for C...
research
∙
04/12/2022
Linearly ordered colourings of hypergraphs
A linearly ordered (LO) k-colouring of an r-uniform hypergraph assigns a...
research
∙
03/04/2022
The Sherali-Adams Hierarchy for Promise CSPs through Tensors
We study the Sherali-Adams linear programming hierarchy in the context o...
research
∙
07/11/2021
CLAP: A New Algorithm for Promise CSPs
We propose a new algorithm for Promise Constraint Satisfaction Problems ...
research
∙
06/28/2021
Additive Sparsification of CSPs
Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC'9...
research
∙
06/13/2021
On rainbow-free colourings of uniform hypergraphs
We study rainbow-free colourings of k-uniform hypergraphs; that is, colo...
research
∙
04/26/2021
Beyond PCSP(1-in-3,NAE)
The promise constraint satisfaction problem (PCSP) is a recently introdu...
research
∙
04/21/2021
QCSP on Reflexive Tournaments
We give a complexity dichotomy for the Quantified Constraint Satisfactio...
research
∙
03/23/2021
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a smal...
research
∙
12/23/2020
PTAS for Sparse General-Valued CSPs
We study polynomial-time approximation schemes (PTASes) for constraint s...
research
∙
07/03/2020
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
Convex relaxations have been instrumental in solvability of constraint s...
research
∙
06/30/2020
Counting Homomorphisms to K_4-minor-free Graphs, modulo 2
We study the problem of computing the parity of the number of homomorphi...
research
∙
03/25/2020
Topology and adjunction in promise constraint satisfaction
The approximate graph colouring problem concerns colouring a k-colourabl...
research
∙
11/20/2019
The complexity of promise SAT on non-Boolean domains
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, G...
research
∙
11/08/2019
Treewidth-Pliability and PTAS for Max-CSPs
We identify a sufficient condition, treewidth-pliability, that gives a p...
research
∙
07/18/2019
Approximate counting CSP seen from the other side
In this paper we study the complexity of counting Constraint Satisfactio...
research
∙
07/04/2019
The Complexity of Approximately Counting Retractions to Square-Free Graphs
A retraction is a homomorphism from a graph G to an induced subgraph H o...
research
∙
07/01/2019
Improved hardness for H-colourings of G-colourable graphs
We present new results on approximate colourings of graphs and, more gen...
research
∙
04/16/2019
Point-width and Max-CSPs
The complexity of (unbounded-arity) Max-CSPs under structural restrictio...
research
∙
01/21/2019
Beyond Boolean Surjective VCSPs
Fulla, Uppman, and Zivny [ACM ToCT'18] established a dichotomy theorem f...
research
∙
01/03/2019
Sparsification of Binary CSPs
A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G ...
research
∙
07/02/2018
The Complexity of Approximately Counting Retractions
Let G be a graph that contains an induced subgraph H. A retraction from ...
research
∙
04/13/2018
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
We analyse the complexity of approximate counting constraint satisfactio...
research
∙
01/07/2018
A tractable class of binary VCSPs via M-convex intersection
A binary VCSP is a general framework for the minimization problem of a f...
research
∙
10/09/2017
The complexity of general-valued CSPs seen from the other side
General-valued constraint satisfaction problems (VCSPs) are generalisati...
research
∙
04/20/2017
On Singleton Arc Consistency for Natural CSPs Defined by Forbidden Patterns
Singleton arc consistency is an important type of local consistency whic...
research
∙
09/18/2015
Backdoors into Heterogeneous Classes of SAT and CSP
In this paper we extend the classical notion of strong and weak backdoor...
research
∙
02/12/2015
Variable and value elimination in binary constraint satisfaction via forbidden patterns
Variable or value elimination in a constraint satisfaction problem (CSP)...
research
∙
01/23/2014
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
The minimisation problem of a sum of unary and pairwise functions of dis...
research
∙
07/10/2013
Tractable Combinations of Global Constraints
We study the complexity of constraint satisfaction problems involving gl...
research
∙
11/12/2008