Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CONSTRAINT SATISFACTION:
Reports tagged with constraint satisfaction:
TR97-012 | 19th March 1997
Luca Trevisan

On Local versus Global Satisfiability

We prove an extremal combinatorial result regarding
the fraction of satisfiable clauses in boolean CNF
formulae enjoying a locally checkable property, thus
solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint
satisfaction ... more >>>


TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

We study the computational complexity of an optimization
version of the constraint satisfaction problem: given a set $F$ of
constraint functions, an instance consists of a set of variables $V$
related by constraints chosen from $F$ and a natural number $k$. The
problem is to decide whether there exists a ... more >>>


TR99-039 | 24th September 1999
Johan Håstad

On approximating CSP-B

We prove that any constraint satisfaction problem
where each variable appears a bounded number of
times admits a nontrivial polynomial time approximation
algorithm.

more >>>

TR01-077 | 24th September 2001
Andrei Krokhin, Peter Jeavons, Peter Jonsson

The complexity of constraints on intervals and lengths

We study interval-valued constraint satisfaction problems (CSPs),
in which the aim is to find an assignment of intervals to a given set of
variables subject to constraints on the relative positions of intervals.
Many well-known problems such as Interval Graph Recognition
and Interval Satisfiability can be considered as examples of ... more >>>


TR03-062 | 10th July 2003
Andrei Krokhin, Peter Jonsson

Recognizing Frozen Variables in Constraint Satisfaction Problems

In constraint satisfaction problems over finite domains, some variables
can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the
instances. We show that the complexity of ... more >>>


TR04-032 | 5th February 2004
Ryan Williams

A new algorithm for optimal constraint satisfaction and its implications

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>


TR04-100 | 23rd November 2004
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>


TR05-005 | 20th December 2004
Tomas Feder

Constraint Satisfaction on Finite Groups with Near Subgroups

Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>


TR05-024 | 8th February 2005
Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>


TR06-021 | 10th February 2006
Tomas Feder

Constraint satisfaction: a personal perspective

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>


TR07-055 | 22nd May 2007
Oliver Kullmann

Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

We consider the next step from boolean conjunctive normal forms to
arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ... more >>>


TR08-008 | 8th February 2008
Venkatesan Guruswami, Prasad Raghavendra

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>


TR08-104 | 23rd November 2008
Madhur Tulsiani

CSP Gaps and Reductions in the Lasserre Hierarchy

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these
problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ... more >>>


TR09-061 | 2nd July 2009
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Optimal Sherali-Adams Gaps from Pairwise Independence

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>


TR10-063 | 12th April 2010
Venkatesan Guruswami, Yuan Zhou

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em
near-satisfiable} instance.

\begin{enumerate}
\item ... more >>>


TR10-132 | 18th August 2010
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

Approximating Linear Threshold Predicates

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>


TR12-074 | 12th June 2012
Venkatesan Guruswami, Yuan Zhou

Approximating Bounded Occurrence Ordering CSPs

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>


TR12-109 | 31st August 2012
Subhash Khot, Muli Safra, Madhur Tulsiani

Towards An Optimal Query Efficient PCP?

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ... more >>>


TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>


TR13-122 | 5th September 2013
Irit Dinur, Venkatesan Guruswami

PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>


TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Håstad

$(2+\epsilon)$-SAT is NP-hard

Revisions: 2

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>


TR14-066 | 17th April 2014
Suguru Tamaki, Yuichi Yoshida

Robust Approximation of Temporal CSP

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>


TR16-029 | 7th March 2016
Joshua Brakensiek, Venkatesan Guruswami

New hardness results for graph and hypergraph colorings

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>


TR16-183 | 16th November 2016
Joshua Brakensiek, Venkatesan Guruswami

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 2

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>>


TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

The Quest for Strong Inapproximability Results with Perfect Completeness

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>


TR18-059 | 6th April 2018
Joshua Brakensiek, Venkatesan Guruswami

Combining LPs and Ring Equations via Structured Polymorphisms

Revisions: 1

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>>


TR19-013 | 31st January 2019
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>


TR19-053 | 5th April 2019
Andrei Krokhin, Jakub Opršal

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


TR19-054 | 9th April 2019
Joshua Brakensiek, Venkatesan Guruswami

Bridging between 0/1 and Linear Programming via Random Walks

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>


TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

Rainbow coloring hardness via low sensitivity polymorphisms

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>


TR20-004 | 17th January 2020
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

Revisions: 1

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>


TR21-026 | 23rd February 2021
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Conditional Dichotomy of Boolean Ordered Promise CSPs

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>


TR21-112 | 30th July 2021
Vikraman Arvind, Venkatesan Guruswami

CNF Satisfiability in a Subspace and Related Problems

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>


TR24-066 | 29th March 2024
Siu On Chan, Hiu Tsun Ng, Sijin Peng

How Random CSPs Fool Hierarchies

Revisions: 1

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), afinfe integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound ... more >>>




ISSN 1433-8092 | Imprint