research
∙
05/29/2022
A note on hardness of promise hypergraph colouring
We show a slightly simpler proof the following theorem by I. Dinur, O. R...
share
research
∙
12/23/2020
PTAS for Sparse General-Valued CSPs
We study polynomial-time approximation schemes (PTASes) for constraint s...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
research
∙
06/12/2020
Sallow: a heuristic algorithm for treedepth decompositions
We describe a heuristic algorithm for computing treedepth decompositions...
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/01/2019
Improved hardness for H-colourings of G-colourable graphs
We present new results on approximate colourings of graphs and, more gen...
research
∙
11/03/2018
Tight complexity lower bounds for integer linear programming with few constraints
We consider the ILP Feasibility problem: given an integer linear program...
research
∙
07/06/2017
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
The notion of Turing kernelization investigates whether a polynomial-tim...
research
∙
07/05/2017