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

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for
every $k$ there is ... more >>>

We take another step in the study of the testability
of small-width OBDDs, initiated by Ron and Tsur (Random'09).
That is, we consider algorithms that,
given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,
need to determine whether $f$ can be implemented
by some restricted class of OBDDs or is far from
more >>>