Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

Andrei Krokhin, Jakub Opršal

We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

The approximate graph colouring problem concerns colouring a $k$-colourable

graph with $c$ colours, where $c\geq k$. This problem naturally generalises

to promise graph homomorphism and further to promise constraint satisfaction

problems. Complexity analysis of all these problems is notoriously difficult.

In this paper, we introduce ...
more >>>