We show an optimal hardness result for the following problem: Given a system of homogeneous linear equations over GF(2) with 3 variables per equation, find a balanced assignment that satisfies maximum number of equations. For arbitrarily small constant ζ > 0, we show that it is hard to determine (in polynomial time) whether such a system has a balanced assignment that satisfies 1-ζ fraction of equations or there is no balanced assignment that satisfies more than ½+ζ fraction of equations. As a corollary, we show that it is hard to approximate (in polynomial time) the Max-Bisection problem within factor 16⁄15-ζ. These hardness results hold under the assumption NP ⊈ ∩ε > 0 DTIME(2nε).Our results are obtained via a construction of a new PCP outer verifier that has a mixing property and a smoothness property. These properties are crucial in the analysis of the inner verifier. No previous outer verifier can achieve both these properties simultaneously. An outer verifier is essentially a 2-query PCP over a large alphabet. Loosely speaking, the mixing property says that the locations of the two queries read by the verifier are uncorrelated. The smoothness property says that the verifier's acceptance predicate is close to being a bijective predicate. Our construction relies on the algebraic techniques used to prove the PCP Theorem. This is in contrast with all earlier constructions that use the PCP Theorem as a black-box. The progress in inapproximability theory seems to require new ideas for building outer verifiers and our construction takes a first step in that direction.

We study nonBoolean 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/spl ges/2, we construct a nonadaptive PCP with perfect completeness and soundness d/sup -1/+d/sup -2/+/spl epsiv/, for any constant /spl epsiv/>0, and an adaptive PCP with perfect completeness and soundness d/sup -1/+/spl epsiv/, for any constant /spl epsiv/>0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d/sup -1/+/spl epsiv/, for any constant /spl epsiv/>0, where four positions are read from the proof. These results match the best known constructions for the case d=2 and our proofs also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold.

As a problem with similar properties to minimum bisection, we consider the following: given a homogeneous system of linear equations over Z/sub 2/, with exactly k variables in each equation, find a balanced assignment that minimizes the number of satisfied equations. A balanced assignment is one which contains an equal number of 0s and 1s. When k=2, this is the minimum bisection problem. We consider the case k=3. In this case, it is NP-complete to determine whether the object function is zero [U. Feige, (2003)], so the problem is not approximable at all. However, we prove that it is NP-hard to determine distinguish between the cases that all but a fraction /spl epsi/ of the equations can be satisfied and that at least a fraction 1/4-/spl epsi/ of all equations cannot be satisfied. A similar result for minimum bisection would imply that the problem is hard to approximate within any constant. For the problem of approximating the maximum number of equations satisfied by a balanced assignment, this implies that the problem is NP-hard to approximate within 4/3-/spl epsi/, for any /spl epsi/>0.

(MATH) We prove that Minimu Vertex Cover on 4-regular hyper-graphs (or in other words, Minimum Hitting Set where all sets have size exactly 4), is hard to approximate within $2 - ε. We also prove that the maximization version, in which we are allowed to pick B = pn elements in an n-vertex hyper-graph, and are asked to cover as many edges as possible, is hard to approximate within 1/(1 — (1—p)4) - ε when p ≤ 1/2 and within ((1—p)4 + p4)/(1 — (1—p)4) — ε when p ξ 1/2. From this follows that the general problem when B is part of the input is hard to approximate within 16/15 - ε.