In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of ``constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier studied ... more >>>

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F of ... more >>>

An instance of a constraint satisfaction problem is $l$-consistent
if any $l$ constraints of it can be simultaneously satisfied.
For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ... more >>>

We consider the problem of testing whether a given system of equations
over a fixed finite semigroup S has a solution. For the case where
S is a monoid, we prove that the problem is computable in polynomial
time when S is commutative and is the union of its subgroups
more >>>

It is well known that coset-generating relations lead to tractable
constraint satisfaction problems. These are precisely the relations closed
under the operation $xy^{-1}z$ where the multiplication is taken in
some finite group. Bulatov et al. have on the other hand shown that
any clone containing the multiplication of some ``block-group'' ... more >>>

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

We introduce symmetric Datalog, a syntactic restriction of linear
Datalog and show that its expressive power is exactly that of
restricted symmetric monotone Krom SNP. The deep result of
Reingold on the complexity of undirected
connectivity suffices to show that symmetric Datalog queries can be
evaluated in logarithmic space. We ... more >>>

We present algebraic conditions on constraint languages \Gamma
that ensure the hardness of the constraint satisfaction problem
CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL.
These criteria also give non-expressibility results for various
restrictions of Datalog. Furthermore, we show that if
CSP(\Gamma) is not first-order definable then it ... more >>>

The well known dichotomy conjecture of Feder and
Vardi states that for every finite family Γ of constraints CSP(Γ) is
either polynomially solvable or NP-hard. Bulatov and Jeavons re-
formulated this conjecture in terms of the properties of the algebra
P ol(Γ), where the latter is ... more >>>

Assuming the existence of one-way functions, we show that there is no
polynomial-time, differentially private algorithm $A$ that takes a database
$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way
marginals are approximately equal to those of $D$. (A two-way marginal is the fraction
of database rows ... more >>>

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.
In this paper, we show that a ... more >>>