Source author record

Andrei Krokhin

Andrei Krokhin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Logic in Computer Science math.AT math.LO math.RA

Catalog footprint

What is connected

6works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

An invitation to the promise constraint satisfaction problem

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been.

preprint2019arXiv

The complexity of 3-colouring $H$-colourable graphs

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 the context of promise constraint satisfaction problems, Brakensiek and Guruswami conjectured that this hardness result extends to promise graph homomorphism as follows: fix any non-bipartite graph $H$ and another graph $G$ with a homomorphism from $H$ to $G$, it is NP-hard to find a homomorphism to $G$ from a given $H$-colourable graph. Arguably, the two most important special cases of this conjecture are when $H$ is fixed to be the complete graph on 3 vertices (and $G$ is any graph with a triangle) and when $G$ is the complete graph on 3 vertices (and $H$ is any 3-colourable graph). The former case is equivalent to the notoriously difficult approximate graph colouring problem. In this paper, we confirm the Brakensiek-Guruswami conjecture for the latter case. Our proofs rely on a novel combination of the universal-algebraic approach to promise constraint satisfaction, that was recently developed by Barto, Bulín and the authors, with some ideas from algebraic topology.

preprint2016arXiv

On Algebras with many symmetric operations

We show that, for each finite algebra A, either it has symmetric term operations of all arities or else some finite algebra in the variety generated by A has two automorphisms without a common fixed point. We also show this two-automorphism condition cannot be replaced by a single fixed-point- free automorphism.

preprint2015arXiv

A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs

In a valued constraint satisfaction problem (VCSP), the goal is to find an assignment of labels to variables that minimizes a given sum of functions. Each function in the sum depends on a subset of variables, takes values which are rational numbers or infinity, and is chosen from a fixed finite set of functions called a constraint language. The case when all functions take only values 0 and infinity is known as the constraint satisfaction problem (CSP). It is known that any CSP with fixed constraint language is polynomial-time equivalent to one where the constraint language contains a single binary relation (i.e. a digraph). A recent proof of this by Bulin et al. gives such a reduction that preserves most of the algebraic properties of the constraint language that are known to characterize the complexity of the corresponding CSP. We adapt this proof to the more general setting of VCSP to show that each VCSP with a fixed finite (valued) constraint language is equivalent to one where the constraint language consists of one $\{0,\infty\}$-valued binary function (i.e. a digraph) and one finite-valued unary function, the latter problem known as the (extended) Minimum Cost Homomorphism Problem for digraphs. We also show that our reduction preserves some important algebraic properties of the (valued) constraint language.

preprint2013arXiv

Oracle Tractability of Skew Bisubmodular Functions

In this paper we consider skew bisubmodular functions as introduced in [9]. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use this extension to show that skew bisubmodular functions given by an oracle can be minimised in polynomial time.

preprint2010arXiv

The complexity of the list homomorphism problem for graphs

We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.