Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

Andrei Bulatov

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

Charanjit Jutla

Venkatesan Guruswami, Kunal Talwar

We prove a strong inapproximability result for routing on directed

graphs with low congestion. Given as input a directed graph on $N$

vertices and a set of source-destination pairs that can be connected

via edge-disjoint paths, we prove that it is hard, assuming NP

doesn't have $n^{O(\log\log n)}$ time randomized ...
more >>>

Andrei A. Bulatov

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite

relational structure H can be expressed as follows: given a

relational structure G over the same vocabulary,

determine the number of homomorphisms from G to H.

In this paper we characterize relational structures H for which

#CSP(H) can be solved in ...
more >>>

Libor Barto, Marcin Kozik

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.

Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ...
more >>>

Venkatesan Guruswami, Euiwoong Lee

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.

The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ...
more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

A Boolean maximum constraint satisfaction problem, Max-CSP\((f)\), is specified by a predicate \(f:\{-1,1\}^k\to\{0,1\}\). An \(n\)-variable instance of Max-CSP\((f)\) consists of a list of constraints, each of which applies \(f\) to \(k\) distinct literals drawn from the \(n\) variables. For \(k=2\), Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>

Andrei Krokhin, Jakub OprÅ¡al

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 ... more >>>

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

- For every $k \geq 1$, there is a monotone function in ${\rm AC^0}$ (constant-depth poly-size circuits) that requires monotone circuits of depth $\Omega(\log^k n)$. This significantly extends a classical result of Okol'nishnikova (1982) and Ajtai ... more >>>

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep

The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $(1-\varepsilon)$-satisfiable (where the parameter is the number of variables) for some constant $0<\varepsilon<1$.

We ... more >>>

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of ... more >>>