All reports by Author Jonas Holmerin:

__
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

__
TR01-094
| 3rd December 2001
__

Jonas Holmerin#### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

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

Jonas Holmerin

We prove that Minimum vertex cover on 4-regular hyper-graphs (or

in other words, hitting set where all sets have size exactly 4),

is hard to approximate within 2 - \epsilon.

We also prove that the maximization version, in which we

are allowed to pick ...
more >>>