All reports by Author Lars Engebretsen:

__
TR02-053
| 20th July 2002
__

Lars Engebretsen, Venkatesan Guruswami#### Is Constraint Satisfaction Over Two Variables Always Easy?

__
TR02-040
| 20th June 2002
__

Lars Engebretsen, Jonas Holmerin#### Three-Query PCPs with Perfect Completeness over non-Boolean Domains

__
TR02-030
| 3rd June 2002
__

Lars Engebretsen, Jonas Holmerin, Alexander Russell#### Inapproximability Results for Equations over Finite Groups

Revisions: 1

__
TR00-089
| 1st December 2000
__

Lars Engebretsen, Marek Karpinski#### Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

__
TR00-042
| 21st June 2000
__

Lars Engebretsen#### Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

Lars Engebretsen, Venkatesan Guruswami

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

Lars Engebretsen, Jonas Holmerin

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

Lars Engebretsen, Jonas Holmerin, Alexander Russell

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

Lars Engebretsen, Marek Karpinski

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

Lars Engebretsen

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