By the breakthrough work of Håstad, several constraint satisfaction
problems are now known to have the following approximation resistance
property: satisfying more clauses than what picking a random
assignment would achieve is NP-hard. This is the case for example for
Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ... more >>>

We study non-Boolean PCPs that have perfect completeness and read
three positions from the proof. For the case when the proof consists
of values from a domain of size d for some integer constant d
>= 2, we construct a non-adaptive PCP with perfect completeness
more >>>

An equation over a finite group G is an expression of form
w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted
variable, or a constant from G; such an equation is satisfiable
if there is a setting of the variables to values in G ... more >>>

The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... more >>>

We show that the k-CSP problem over a finite Abelian group G
cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for
any constant epsilon>0, unless P=NP. This lower bound matches
well with the best known upper bound, |G|^{k-1}, of Serna,
Trevisan and Xhafa. The proof uses a combination of PCP
techniques---most notably a ... more >>>