The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora^{∗}

CS Division U. C. Berkeley

László Babai^{†}

University of Chicago and Eötvös University, Hungary

Jacques Stern

Laboratoire d’Informatique Ecole Normale Supérieure

Z Sweedyk^{‡}

CS Division U. C. Berkeley

Abstract

We prove the following about the Nearest Lattice Vector Problem (in any ℓ_{p} norm), the Nearest Codeword Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems.

1. Approximating the optimum within any constant factor is NP-hard.

2. If for some ϵ > 0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2^{log^{0.5−ϵ} n} then NP is in quasi-polynomial deterministic time: NP ⊆ DTIME(n^{poly(log n)}).

Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the ℓ_{∞} norm.

Improving the factor 2^{log^{0.5−ϵ} n} to \sqrt{dim} for either of the lattice problems would imply the hardness of the Shortest Vector Problem in ℓ_{2} norm; an old open problem.

Our proofs use reductions from few-prover, oneround interactive proof systems [FL], [BG+], either directly, or through a set-cover problem.

1 Introduction

An algorithm is said to approximate a positive integer-valued function f within factor c if on every input x its output is within a factor c of f(x). (Hence the closer c is to 1, the better the approximation.) In this paper we demonstrate that approximating certain NPhard functions is computationally intractable. The functions considered include well-known minimum distance problems for integral lattices and linear codes as well as the problem of finding a largest feasible subsystem of a system of linear equations (or inequalities) over Q. Our result is that approximating these functions (even to within very large factors) is either NPhard or almost NP-hard. A function f is almost-NP-hard if using f as an oracle, we could recognize any NP language in deterministic quasi-polynomial time, i.e. in time O(n^{poly(log n)}), where n is the length of the input.

An integral lattice L(b_{1}, …, b_{m}) in R^{n}, generated by the basis {b_{1}, …, b_{m}} is the set of all linear combinations ∑_{i=1}^{m} α_{i}b_{i}, where the {b_{i}} is a set of independent vectors in Z^{n} and α_{i} ∈ Z.

Definition 1 (Shortest Vector Problem in ℓ_{p} norm, SV_{p}): Given a basis {b_{1}, …, b_{n}}, find the shortest non-zero vector (in ℓ_{p} norm) in L(b_{1}, …, b_{n}) .

Definition 2 (Nearest Vector Problem in ℓ_{p} norm, NV_{p}): Given a basis {b_{1}, …, b_{n}}, and a point b_{0} ∈ Q^{n}, where b_{0} ≠ 0, find the nearest vector (in ℓ_{p} norm) in L(b_{1}, …, b_{n}) to b_{0}.

The SV problem is particularly important because even relatively poor polynomial-time approximate solutions to it (within c^{m}, [L^{3}]) have been used in a host of applications, including integer programming, solving low-density subset-sum problems and breaking knapsack-based codes [LO], simultaneous diophantine approximation and factoring polynomials over the rationals [L^{3}], and strongly polynomial-time algorithms in combinatorial optimization [FT]. For details and more applications, especially to classical problems in the “geometry of numbers”, see the surveys by Lovász [Lov] or Kannan [K].

Lovász’s celebrated lattice transformation algorithm [L^{3}] runs in polynomial time and approximates SV_{p} (p ≥ 1) within c^{m}. A modification of this algorithm [Bab] yields the same for NV_{p}. Schnorr modified the Lovász algorithm and obtained, for every ϵ > 0, approximations within O(2^{ϵm}) in polynomial time for these problems [Sch].

∗Supported by an IBM Graduate Fellowship.

†Partially supported by NSF grant CCR-9014562.

‡Partially supported by NSF grant CCR-9201092 and Sandia National Laboratories

On the other hand, Van Emde Boas showed that NV_{p} is NP-hard for all p ≥ 1 ([vEB]; see [K] for a simpler proof). Lagarias showed that the shortest vector problem is NP-hard under the ℓ_{∞} (i.e. max) norm. But it is still an open problem whether SV_{p} is NPhard for any other p, and specifically for p = 2.

While we do not solve this open problem, we obtain hardness results for the approximate solutions of the known NP-hard cases.

We follow the example of recently established links between the theory of interactive proofs and the hardness of approximation; and add some new links (cf. [FG+], [AS], [AL+], [LY], [Z], [BG+]).

In the following theorems, LARGE factors mean factors 2^{log^{0.5−ϵ} n} where ϵ > 0 is fixed and n = input size.

Theorem 1 1. Approximating NV_{p} (i) within any constant factor c ≥ 1 is NP-hard; (ii) within any LARGE factor is almost-NP-hard.

2. Approximating SV_{∞}within any LARGE factor is almost-NP-hard.

Our reductions use only (0, ±1)-vectors. Hence the problems remain hard in that subcase.

We mention that improving the LARGE factors in either of the above results to \sqrt{d} (d = dimension) would prove hardness of SV_{2}, a long standing open question. The reason is that approximating either SV_{∞} or NV_{2} to within a factor \sqrt{d} is reducible to SV_{2}. To see this for SV_{∞}, notice that the solutions in SV_{∞} and SV_{2} are always within a factor \sqrt{d} of each other. For NV_{2} the implication follows from Kannan’s result [K] that approximating NV_{2} within a factor Ω(\sqrt{d}) is reducible to SV_{2}.

We also note that approximating NV_{2} within any factor greater than d^{1.5} is unlikely to be NP-complete, since Lagarias et al. [LLS] have shown that this problem lies in NP ∩ co-NP.

Our results, like other recent “inapproximability” results, use ideas involving few-prover single-round interactive membership proofs for NP. Specifically, we use a theorem of Feige and Lovász [FL].

We derive hardness results for a number of other problems which in one way or another involve distances of vectors. Next, we define these problems. Nearest-Codeword: INPUT : An m × n matrix

A over GF (2) and a vector y ∈ GF (2)^{n}. OUTPUT : A vector x ∈ GF (2)^{m} minimizing the Hamming distance between xA and y.

Max-Satisfy INPUT : A system of m equations in n variables over Q.

OUTPUT : (Size of the) largest subset of equations that is a feasible system.

Min-Unsatisfy INPUT : A system of m equations in n variables over Q. OUTPUT : (Size of) The smallest set of equations whose removal makes the system feasible.

Observe that a solution to MAX-SATISFY is exactly the complement of a solution to MIN-UNSATISFY, and therefore the two problems have the same complexity. (Indeed, it is known that both are NP-hard; this is implicit e.g. in [JP]). However, the same need not be true for approximate solutions. For instance, vertex-cover and independent-set are another “complementary” pair of problems, and seem to differ greatly in how well they can be approximated in polynomial time. (Vertex cover can be approximated within a factor 2, and independent-set is NP-hard up to a factor n^{c} for some c > 0 [FG+, AS, AL+].)

Theorem 2 Approximating any of MIN-UNSATISFY and NEAREST-CODEWORD within any constant factor is NP-hard and within any LARGE factor is almost-NP-hard.

→

is this theorem right?

Theorem 3 Approximating MAX-SATISFY within afactor of n^{a} is NP-hard for some a > 0.

We know of no good approximation algorithms for any of these problems. Kannan has shown us a simple polynomial time algorithm that uses Helly’s theorem to approximate MIN-UNSATISFY within a factor of n + 1.

Finally, we consider a well-known problem in learning theory: learning a halfspace in the presence of malicious errors. (The context in which the problem arises is that of training a perceptron, a learning model first studied by Minsky and Papert [MP].) Rather than describing the learning problem in the usual PAC setting, we merely present the underlying combinatorial problem.

The input to the learner consists of a set of m points in R^{n}, each labelled with + or −. (These should be considered as positive and negative examples of a concept.) The learner’s output is a hyperplane, a · x = b (a, x ∈ R^{n}, b ∈ R). The hypothesis is said to correctly classify a point marked + (resp. −) if that point, say y satisfies a · y > b (a · y < b, resp.). Otherwise it is said to misclassify the point.

Finding a hypothesis that minimizes the number of misclassfications is the open hemispheres problem, which is NP-hard [GJ]. Define the error of the algorithm as the number of misclassifications by its hypothesis, and the noise of the sample as the error of the best possible algorithm. Let the failure ratio of the algorithm be the ratio of the error to noise.

Theorem 4 Achieving any constant failure ratio is NP-hard and achieving any LARGE failure ratio is almost-NP-hard.

This confirms what has been conjectured in learning theory [HS]. A failure ratio ≤ n can be achieved by Kannan’s idea, mentioned above.

Better Factors For the following problems we can prove hardness up to a factor 2^{log^{1−ϵ} n} instead of 2^{log^{0.5−ϵ} n}: NV_{p}, NEAREST-CODEWORD.

2 Organization of the Paper

Although the various problems mentioned in the introduction may appear to be very different, they are proved hard to approximate with very similar reductions (except MAX-SATISFY which has a different reduction). In Section 3 we show the hardness of constant-factor approximations for all the problems. Although this reduction is fairly simple, it will help illustrate some of the ideas used subsequently in Section 4 where the hardness of approximating up to LARGE factors will be shown. Another purpose of Section 3 is to show the connection between the reductions to the different problems described in the introduction. Section 5 completes the proof of the hardness result by showing hardness of an intermediate problem called Label Covering. Section 5 also proves an expansion-type lemma for the geometry underlying the Feige-Lovász protocol. Section 6 proves the hardness result for MAX-SATISFY. Section 7 provides a different reduction for factors slightly better LARGE.

3 Constant Factors

In this section we prove the following theorem.

Theorem 5 For any constant c > 1, approximating the following problems within a factor c is NPcomplete: (i) NV_{p} for p ≥ 1 (ii) NEAREST-CODEWORD (iii) MIN-UNSATISFY (iv) Minimum Failure Ratio while learning a halfspace in presence of errors.

We use the reduction to set-cover given by Bellare et al. [BG+], which improves the reduction due to Lund and Yannakakis [LY]. Recall that an instance of set-cover consists of a ground-set U and a collection of subsets S_{1}, S_{2}, …, S_{m} of U. A cover is a subcollection of the S_{i}’s whose union is U. The cover is said to be exact if the sets in the cover are pairwise disjoint. The following result appears in [BG+].

Proposition 6 [BG+] For every c > 1 there is a polynomial time reduction that transforms an instance φ of SAT into an instance of set-cover and integer K, such that if φ is satisfiable, there is an exact cover of size K, and otherwise no set cover has size less than c · K.

Proof of Theorem 5. Let (U, S_{1}, …, S_{m}), K be the instance of set-cover obtained in Proposition 6. We transform it to an instance of NV_{1}: b_{0} and L(b_{1}, …, b_{m}), such that the optimum is either K or ≥ c · K depending on the satisfiability of φ.

The vectors have |U| + m coordinates. Let L = c · K. The point b_{0} is the vector having L in the first |U| coordinates, followed by m 0’s. The i’th basis vector b_{i} is (L·χ_{S_{i}}, 0, …, 0, L, 0, …, 0) (the L appears in position |U| + i). Here χ_{S_{i}} is the characteristic vector of the set S_{i} (i.e. the vector which has a 1 in a coordinate corresponding to an element in S_{i} and 0 otherwise).

Let OPT = min || − b_{0} + ∑_{i} α_{i} · b_{i}||_{1}, α_{i} ∈ Z. Just the contribution from the last m coordinates shows || − b_{0} + ∑_{i} α_{i} · b_{i}||_{2} ≥ ∑_{i} |α_{i}|, with equality holding iff the first |U| coordinates are 0. Furthermore, if any of the first |U| coordinates is not 0, then it is at least L, in which case ||−b_{0} +∑_{i} α_{i} ·b_{i}||_{1} ≥ L+∑_{i} |α_{i}| ≥ cK.

If there is an exact cover (S_{i_{1}}, S_{i_{2}}, …, S_{i_{K}}), the vector ∑_{j=1}^{K} b_{i_{j}} has ℓ_{1} distance K from b_{0}. (Note that the exactness of the cover is crucial).

Now suppose no cover has size less than c·K. Then we show OPT ≥ min {L, c · K},which is ≥ cK. Consider, for any integer assignment to α_{i}’s, the collection of subsets {S_{i} : α_{i} ≠ 0}. If these sets form a set-cover, then ∑_{i} |α_{i}| ≥ c · K. If they do not, then one of the coordinates in −b_{0}+∑_{i} α_{i}·b_{i} is at least L. This proves our result for NV_{1}.

NV_{1} with 0/1 vectors. Replace each of the first |U| coordinates by a set of L new coordinates. If a vector had an L in the original coordinate, it has a 1 in each of the new L coordinates, and 0 otherwise.

Other Finite Norms. Changing the norm from ℓ_{1} to ℓ_{p} changes the gap from c to ^{p} \sqrt{c}, hence the result claimed for ℓ_{p} norms also follows.

l_{∞} Norm. Assume some canonical ordering of subsets of S = \{S_{1}, …, S_{m}\} of size cK. Let m′ = \binom{m}{cK}.

Consider the 2^{cK} × cK matrix whose rows are all binary vectors of length cK over {−1, 1}. Let β_{i} be the i-th column of this matrix.

The vectors will have |U|+m′2^{cK} coordinates. The vector b_{0} is the same in the first |U| coordinates as the fixed vector the NV_{1} reduction. The remaining coordinates are set to 0. Similarly, the i’th basis vector, b_{i}, has L·χ_{S_{i}} in the first |U| coordinates. The remaining m′2^{cK} coordinates will be paritioned into blocks of size 2^{cK}; each block will be associated with one of the subset of S. If S_{i} is the m-th set of the j-th subset of S in the canonical ordering, then the j-th block of b_{i} is set to β_{m}. If S_{i} does not occur in the j-the subset, then the block is set to 0 in b_{i}.

As in the NV_{1} reduction, any vector with an L in each of the first |U| coordinates must correspond to a set-cover. If φ is satifiable this cover has size K. Further, by construction each of the last m′2^{cK} will be at most K (since the weights assigned to the basis vectors are all 1). If φ is not satisfiable, then every set cover has size at most cK. It is easy to see that the vector associated with such a set cover must have a value at least cK in one of the last coordinates m′2^{cK} coordinates.

Nearest-Codeword. View the vectors b1^{′}, …, bm^{′} obtained from the reduction to “NV_{1} with 0/1 vectors” as generators of a binary code. Let the received message be b0^{′}. Then the minimum distance of b0^{′} to a codeword is exactly K in one case and c · K in the other.

Min-Unsatisfy. Consider the instance b0^{′}, b1^{′}, …, bm^{′} again. Each vector has m + L · |U| coordinates. This instance implicitly defines the following system of m+ L · |U| equations in m variables :

−b0^{′} + ∑ α_{i} · bi^{′} = 0,

where the α_{i}’s are the variables and 0 is the vector whose all coordinates are 0. The structure of the problem assures us that if we satisfy the first L · |U| equations, then the non-zero variables must yield a setcover (and then each nonzero variable gives rise to an unsatisfied equation among the last m ones). Thus the minimal number of equations that must be removed in order to yield a satisfiable system is K in one case, and ≥ c · K in the other.

Learning Halfspaces. Notice that minimizing the failure ratio involves solving the following problem: Given a system of strict linear inequations, find the smallest subset of inequalities whose removal from the system makes it feasible. Now we take the system of equations in the MIN-UNSATISFY reduction and replace each equation by two inequalities in the obvious way. This does not give a system of strict inequalities, however, it does give a gap in the number of inequations that must be removed in order to make the system feasible. The inequalities can be made strict (for this special case) by introducing a new variable δ and changing each inequation ... + .. ≥ 0 to ... + .. + δ > 0, at the same time introducing L identical new inequations δ < 1/L. It is now easily seen that any solution to the largest feasible subsystem must have δ < 1/L, which in turn forces the variables to be 0/1.

A Comment We note that the reduction depends crucially upon the fact that the cover is exact in the case that φ is satisfiable. Such peculiarities seem inherent in recent non-approximability results. For instance, the hardness result for Chromatic Number in [LY] depends upon very specific properties of the graph obtained in the clique reductions of [FG+, AS, AL+].

4 Large Factors

In this section we prove the following theorem.

Theorem 7 Approximating each of the following problems up to LARGE factors (as defined in the introduction) is almost-NP-hard: (i) NV_{p} for any p ≥ 1. (ii) SV_{∞} (iii) NEAREST-CODEWORD (iv) Minimum Failure Ratio while learning a halfspace in presence of errors (v) MIN-UNSATISFY.

We will show the result only for NV_{1} and SV_{∞}; the hardness results for the other problems will follow from the NV_{1} result exactly as in Theorem 5.

The reductions in this section are from certain problems involving label-covers for bipartite graphs. The hardness of approximating these covering problems is proved in Lemmas 8 (used in the reduction to NV_{1}) and 9 (used in the reduction to SV_{∞}). These hardness results use a theorem of Feige and Lovász [FL] about the existence of efficient 2-prover, 1-round interactive proofs for NP. In this respect, our reductions are similar to previous reductions in [Bel, BR, LY, BG+], and are closest in spirit to the reduction to set-cover given by Lund and Yannakakis [LY]. However, proving the correctness of our reduction to SV_{∞} involves delving into the geometric structure of the Feige-Lovász proofsystem, and it is an open problem whether there are reductions based on simpler principles.

4.1 The Label-Cover Problem

The input to the label-cover problem is a bipartite graph G = (V_{1}, V_{2}, E) (where E ⊆ V_{1} × V_{2}), and a set of possible labels B_{1} and B_{2} for vertices in V_{1} and V_{2} respectively. Also included in the input is a relation Π ⊆ E × B_{1} × B_{2} that consists of admissible pairs of labels for each edge. A labelling of the graph is a pair of functions (P_{1}, P_{2}) where P_{i} : V_{i} → 2^{B_{i}} for i = 1, 2; in other words, (P_{1}, P_{2}) assigns a set of labels – possibly empty – to each vertex of the graph. The l_{1}-cost of the labelling is ∑_{v∈V_{1}} |P_{1}(v)| and its ℓ_{∞}- cost is max_{v∈V_{1}}|P_{1}(v)|. A labelling is said to cover an edge (v_{1}, v_{2}) if both P_{1}(v_{1}) and P_{2}(v_{2}) are nonempty and for every label b_{2} ∈ P_{2}(v_{2}) there exists a b_{1} ∈ P_{1}(v_{1}) such that (e, b_{1}, b_{2}) ∈ Π. A total-cover of G is a labelling that covers every edge.

It is a simple exercise to see that it is NP-hard to find the minimum cost (under any ℓ_{p} norm) of these covers. Furthermore, it is implicit in the calculations of [LY] that it is almost-NP-hard to obtain even weak approximations to these costs. Here we restate this result in a more exact form.

Lemma 8 For each fixed ϵ > 0 there is a quasipolynomial time reduction that reduces an instance φ of SAT of size n to an instance of label-cover (G, B_{1}, B_{2}, Π) of size N (N ≤ 2^{poly(log n)}) such that

• If φ is satisfiable, there is a total-cover with l_{1}- cost = |V_{1}| and ℓ_{∞}-cost = 1.

• If φ is not satisfiable then any labelling that covers more than \frac{1}{2} the edges (in particular, every totalcover) has l_{1}-cost ≥ 2^{log^{0.5−ϵ} N} · |V_{1}| and ℓ_{∞}-cost ≥ 2^{log^{0.5−ϵ} N}.

The reduction has the property that every vertex in V_{1} has the same degree. Furthermore, for each e ∈ E and b_{1} ∈ B_{1} there is at most one b_{2} ∈ B_{2} such that (e, b_{1}, b_{2}) ∈ Π.

The proof of Lemma 8 appears in Section 5. For the reduction to SV_{∞}we’ll need to prove the hardness of a related (and not very natural) covering problem.

Definition 3 Let (G, B_{1}, B_{2}, Π) be an instance of label-cover and (P_{1}, P_{2}) be a labelling. An edge e = (v_{1}, v_{2}) is untouched by the labelling if P_{1}(v_{1}) and P_{2}(v_{2}) are empty sets. It is cancelled if P_{2}(v_{2}) is empty, P_{1}(v_{1}) is not empty, and for every b_{1} ∈ P_{1}(v_{1}) there is an b′_{1} ∈ P_{1}(q_{1}) such that both (e, b_{1}, b_{2}) and (e, b′_{1}, b_{2}) are in Π for some b_{2} ∈ B_{2}.

Definition 4 A labelling (P_{1}, P_{2}) is a pseudo-cover if it assigns a label to some vertex, and every edge is either untouched, cancelled or covered.

One of our main theorems is that approximating the minimum ℓ_{∞}-cost of a pseudo-cover is hard.

Lemma 9 In the label covering problem constructed in Lemma 8, if φ is satisfiable, there is a pseudo-cover with ℓ_{∞} cost 1. If φ is not satisfiable every pseudocover has ℓ_{∞} cost 2^{log^{0.5−ϵ} N}.

The first part of the lemma follows from Lemma 8, since a total-cover is also a pseudo-cover. The more difficult second half is left to Section 5.

4.2 Vectors for NV_{1} and SV_{∞}

Given an instance of label-cover obtained from the previous section we construct a corresponding set of vectors. Certain linear combinations of these vectors will correspond to total-covers or pseudo-covers.

First we simplify the structure of the relation Π in the instance of label-cover of Lemma 8 by restricting the labels admissible at vertex v_{1} ∈ V_{1} to only valid labels. A label b_{1} is valid for v_{1} if, for every edge e incident to v_{1}, there is a label b_{2} such that (e, b_{1}, b_{2}) ∈ Π; in other words, b_{1} can be used to cover all edges incident to v_{1}. The reason for restricting attention to valid labels is that when φ is satisfiable, the labelcover uses only 1 label for a vertex, so the label used must be valid. And if φ is not satisfiable, restricting the set of possible (vertex, label) pairs to be valid can only increase the minimum cost of a label-cover.

The basis set contains a vector V_{[v_{i},b_{i}]} for each valid pair (v_{i}, b_{i}), i.e. where v_{i} ∈ V_{i} and b_{i} ∈ B_{i} (i = 1, 2), and when i = 1, b_{1} is valid for v_{1}. Any linear combination of these vectors implicitly defines a labelling of the graph G.

Definition 5 Let x = ∑ c_{[v_{i},b_{i}]} · V_{[v_{i},b_{i}]} be a linear combination of the vectors in the set, where the coefficients c_{[v_{i},b_{i}]} are integers. The labelling defined by the vector x, denoted (P_{1}^{x}, P_{2}^{x}), is P_{i}^{x}(v_{i}) = {b_{i} | c_{[v_{i},b_{i}]} ≠ 0}, for i = 1, 2.

Recall from Lemma 8 that for a fixed pair e, b_{1}, there is a unique label b_{2} such that (e, b_{1}, b_{2}) ∈ Π. We denote such a b_{2} by b_{2}[e, b_{1}].

Each vector in our set has |E|(1+|B_{2}|) coordinates; 1 + |B_{2}| coordinates for each e ∈ E. The coordinates corresponding to e in a vector is referred to as its eprojection.

For j = 1, 2, …, |B_{2}|, let u_{j} be a vector with 1+|B_{2}| coordinates, in which the j’th entry is 1 and all the other entries are 0. With some abuse of notation we’ll associate the vector u_{b_{2}} with the label b_{2} ∈ B_{2}.

For v_{2} ∈ V_{2}, b_{2} ∈ B_{2}, the e-projection of the vector V_{[v_{2},b_{2}]} is u_{b_{2}} if e is incident to v_{2}; and 0 otherwise.

For each valid pair v_{1}, b_{1}, the e-projection of the vector V_{[v_{1},b_{1}]} is 1 − u_{b_{2}[e,b_{1}]} if e is incident to v_{1}; and 0 otherwise.

Here 0 and 1 are the all-zero vector and iall-one vector, resp. Notice that the e-projections of the vectors form a multi-set comprised of exactly one copy of the vector u_{b_{2}} for each b_{2} ∈ B_{2}, and zero or more copies of the vector 1 − u_{b_{2}}, plus multiple copies of 0.

In the reductions that follows we shall be interested in linear combinations of the vectors {V_{[v_{i},b_{i}]}} that sum to a multiple of 1 or to 0. In particular we will look at the e-projections of such sums, whose behavior is described by the following simple lemma.

Lemma 10 Let X be the set of vectors {u_{b_{2}}|b_{2} ∈ B_{2}} and Y a multiset over {1 − u_{b_{2}}|b_{2} ∈ B_{2}}. Let z be a

linear combination of these vectors such that z = α1. Then for each b_{2} ∈ B_{2} i. If the coefficient of u_{b_{2}} is nonzero, there is some

vector in Y of the form 1 − u_{b_{2}} with nonzero coefficient.

ii. If the coefficient of u_{b_{2}} is 0 then the number of vectors in Y of the form 1 − u_{b_{2}} with nonzero coefficients is either 0 or ≥ 2.

Further, if α ≠ 0, then some vector in X has a nonzero coefficient in the combination.

Proof: The vectors {u_{1}, …, u_{|B_{2}|}} are linearly independent and do not span 1. Therefore if ∑_{b_{2}}(c_{b_{2}} · u_{b_{2}} + d_{b_{2}} · (1 − u_{b_{2}})) = α1, then c_{b_{2}} = d_{b_{2}} for all b_{2}. The claims follow.

Corollary 11 If x is a nontrivial linear combination of the vectors {V_{[v_{i},b_{i}]}} and x = α1, then (P_{1}^{x}, P_{2}^{x}) is a pseudo-cover of G. If α ≠ 0, this pseudo-cover is a total-cover.

Proof: For any edge e, the e-projections of the vectors {V_{[v_{i},b_{2}]}} form a system described in the hypothesis of Lemma 10. Then case (i) of the lemma corresponds to e being covered, and case (ii) to e being either cancelled or untouched. Thus (P_{1}^{x}, P_{2}^{x}) is a pseudo-label cover. When α ≠ 0, then case (i.) holds for each edge (for some b_{2}), so each edge is covered.

4.3 Hardness of Approximating NV_{1}

The set of vectors {V_{[v_{i},b_{i}]}} defined in Section 4.2 has the property that any linear combination of them that sums to 1 defines a total-cover. This fact is used in the following reduction.

Theorem 12 There is a polynomial time transformation from the instance of label-cover in Lemma 8 to an instance of NV_{1} such that the optimum in the NV_{1} instance has cost ≥ minimum ℓ_{1}-cost of a total-cover. Further, if there is a total-cover of ℓ_{1}-cost |V_{1}|, then the optimum is also |V_{1}|.

Proof: The vectors in the instance of NVP have |E| · (1+|B_{2}|)+|V_{1}|·|B_{1}| dimensions. Let L be the integer |E| · (1 + |B_{2}|). The fixed point, W_{0}, will have an L in each of the first |E|(1 + |B_{2}|) dimensions and 0 elsewhere.

The basis of the lattice consists of a vector, W_{[v_{i},b_{i}]} for every valid (vertex,label) pair (v_{i}, b_{i}). In the first |E| · (1 + |B_{2}|) coordinates, the vector W_{[v_{i},b_{i}]} equals L·V_{[v_{i},b_{i}]}. We think of the last |V_{1}|·|B_{1}| coordinates as being identified one-to-one with a pair (v_{1}, b_{1}). Then the coordinate identified with (v_{1}, b_{1}) contains 1 in W_{[v_{1},b_{1}]} and 0 in all other vectors. This makes the last |V_{1}| · |B_{1}| coordinates suitable for counting, as shown in the next observation.

Claim: Let x = ∑ c_{[v_{i},b_{i}]} · W_{[v_{i},b_{i}]} be a vector in the lattice. Then || − W_{0} + x||_{1} ≥ ℓ_{1}-cost of (P_{1}^{x}, P_{2}^{x}).

The claim follows from the observation that any of last |V_{1}|·|B_{1}| coordinates of x that is not 0 corresponds to a label assigned to some q_{1} node by P_{1}^{x}.

Now let OPT be the minimum ℓ_{1} cost of a totalcover. We show that every vector x in the lattice satisfies || − W_{0} + x||_{1} ≥ min {L, OPT}. Notice that each entry of W_{0} − x in the first |E|(1 + |B_{2}|) dimensions is a sum of integer multiples of L. If it isn’t 0, its magnitude is ≥ L, and so || − W_{0} + x||_{1} ≥ L. On the other hand, if all those entries are 0 then, by Corollary 11, (P_{1}^{x}, P_{2}^{x}) is a total-cover, and so by the above claim || − W_{0} + x||_{1} ≥ OPT.

Finally, if there is a total-cover of ℓ_{1}-cost |V_{1}|, then the following vector has length |V_{1}|. x = −W_{0} + ∑_{v_{1}∈V_{1}} W_{[v_{1},P_{1}(v_{1})]} + ∑_{v_{2}∈V_{2}} W_{[v_{2},P_{2}(v_{2})]}.

4.4 Hardness of Approximating SV_{∞}

The set of vectors {V_{[v_{i},b_{i}]}} defined in Section 4.2 has the property that any non-trivial linear combination of them that sums to 0 defines a pseudo-cover. This fact is used in the following reduction.

Theorem 13 There is a polynomial time transformation from the instance of label-cover in Lemma 8 to an instance of SV_{∞}such that the solution to the SV_{∞}instance is ≥ minimum ℓ_{∞}-cost of a pseudocover. Further, if there is a total-cover of ℓ_{∞}-cost 1, then the solution is 1.

The reduction uses an ℓ × ℓ Hadamard matrix i.e. a (±1) matrix such that H_{ℓ}^{t}H_{ℓ} = ℓI_{ℓ}. (H_{ℓ} exists e.g. when ℓ is a power of 2, cf. [Bol, p.74]).

Claim: Let z ∈ Z^{ℓ}. If z has at least k nonzero entries then ||H_{ℓ}z||_{∞} ≥ \sqrt{k}. Proof: The columns of \frac{1}{\sqrt{ℓ}}H_{ℓ} form an orthonormal

basis. Hence ||\frac{1}{\sqrt{ℓ}}H_{ℓ}z||_{2} = ||z||_{2} ≥ \sqrt{k}.

Proof of Theorem 13. Let L be the integer |E| |B_{2}|. The vectors in the lattice have |E| · (1 + |B_{2}|) + |V_{1}| · |B_{1}| coordinates. The basis of the lattice consists of a vector W_{[v_{i},b_{i}]} for each each valid (vertex, label) pair v_{i}, b_{i}, and an additional vector, W_{0}, that has L in each of the first |E|·(1+|B_{2}|) coordinates and 0 elsewhere.

As in the last reduction, W_{[v_{i},b_{i}]} will equal L·V_{[v_{i},b_{i}]} in the first |E| · (1 + |B_{2}|) coordinates. The remaining |V_{1}| · |B_{1}| coordinates will be viewed as blocks of |B_{1}| coordinates, each associated with a v_{1} ∈ V_{1}. We refer to entries in the block associated with v_{1} as v_{1}- projection of the vector.

We may assume there exists a Hadamard matrix H_{ℓ} for ℓ = |B_{1}|. With each label b_{1} ∈ B_{1} we identify a unique column vector of H_{l}, denoted h_{b_{1}}. Then the v_{1}-projection of W_{[v,b]} is h_{b} if v = v_{1} and 0 if v ≠ v_{1}.

Let OPT be the minimum ℓ_{∞}-cost of a pseudocover. For any vector x in the lattice, the entry in any of the first |E|(1 + |B_{2}|) coordinates is a sum of integer multiples of L, so if it is not 0, its magnitude is ≥ L, and hence ≥ OPT. So all these entries must be 0. But then by Lemma 11, we conclude that the labelling defined by x is a pseudo-cover, and must therefore assign ≥ OPT labels to some v_{1} ∈ V_{1}. But then ||x||_{∞} ≥ \sqrt{OPT} by the Claim.

Now suppose OPT = 1 and (P_{1}, P_{2}) achieves it. Then the following vector has ℓ_{∞} norm 1.

−W_{0} + ∑_{v_{1}∈V_{1}} W_{[v_{1},P_{1}(v_{1})]} + ∑_{v_{2}∈V_{2}} W_{[v_{2},P_{2}(v_{2})]}.

5 Hardness of Label Covers

In this section we prove Lemmas 8 and 9. To do so, we’ll need some facts about 2-Prover 1-Round Interactive Proof Systems.

5.1 2-Prover 1-Round Interactive Proofs

A 2-Prover 1-Round interactive proof system for a language L consists of a probabilistic polynomialtime verifier V which interacts with two all-powerful deterministic provers. The provers want to convince the verifier that the input, x, belongs to L.

For a fixed input, there are five sets associated with the protocol: Q_{1}, Q_{2}, R, A_{1}, A_{2}. The verifier consists of two polynomial time computable functions, q_{1} and q_{2}, where q_{i} : R → Q_{i} (query generation), and a polynomial-time predicate Ψ : R × A_{1} × A_{2} → {0, 1}. The provers are functions P_{i} : Q_{i} → A_{i}.

The verifier begins the protocol by picking an r ∈ R uniformly at random (this is its “random seed”). Then it computes the query q_{i}[r] ∈ Q_{i} and sends it to prover P_{i} (i = 1, 2). Prover P_{i} responds with a_{i} = P_{i}(q_{i}[r]). Finally the verifier decides whether to accept or reject according to the value Ψ(r, a_{1}, a_{2}).

It is implicit in [FL] that for every polynomial-time computable function k(n), there is a 2-prover 1-round proof-system for 3SAT such that

• If φ ∈ 3SAT then there exist provers such that the verifier always accepts (i.e. for every choice of r).

• If φ ∉ 3SAT then for any pair of provers the verifier accepts with probability at most 2^{−k(n)} (where n = size of φ).

• |R|, |Q_{i}|, |A_{i}| ≤ 2^{f(k(n),log(n))}, where f is a bivari-

ate polynomial. We give a specific protocol in section 5.4 with f(k(n), log(n)) = k^{2}(n) log^{2}(n). ^{→} Further, it is a check this feature of this protocol that for a fixed r ∈ R and a fixed a_{1} ∈ A_{1}, there is at most one a_{2} ∈ A_{2} such that the verifier accepts, i.e. Ψ(r, a_{1}, a_{2}) = 1.

5.2 Reduction to Label Cover

The proofs of Lemmas 8 and 9 are based on the same reduction from 3SAT to Label Cover; in the former case we are looking for a total cover and in the latter a pseudo-cover.

For a 3SAT instance, φ, we construct the sets R, Q_{i}, A_{i}, i = 1, 2 associated with the interative proof protocol. Then the graph of the label cover instance is (V_{1}, V_{2}, E) where V_{i} = Q_{i}, for i = 1, 2 and E = {(q_{1}[r], q_{2}[r]) : r ∈ R}. The set of labels are B_{i} = A_{i} for i = 1, 2. The relation Π is exactly the predicate Ψ computed by the verifier, i.e.

Π = {(e, b_{1}, b_{2}) : (∃r)(e = (q_{1}[r], q_{2}[r])&Ψ(r, b_{1}, b_{2}) = 1}).

5.3 Hardness of Total Covers

We can now prove Lemma 8.

If φ ∈ 3SAT, there exist provers P_{1} and P_{2} that make the verifier accept with probability 1 (i.e. for every choice of r). Since a prover P_{i} is an assignment of one answer to each query, and this assignment makes the verifier accept for every random integer r (equivalently, for every edge in the above graph), we conclude that (P_{1}, P_{2}) form a total-cover with l_{1}-cost of Q_{1} (= |V_{1}|) and ℓ_{∞}-cost 1.

Now suppose φ ∉ 3SAT. So no provers can satisfy the verifier with probability more than 2^{−k(n)}. Hence in the label-cover instance, no labelling using at most 1 label per vertex can cover more than a fraction 2^{−k(n)} of the edges.

Now suppose there is a labelling that covers \frac{1}{2} the edges at ℓ_{1}-cost less than 2^{k(n)} · |V_{1}|. Let G′ be the subgraph of G consisting of all the edges covered by (P_{1}, P_{2}). Construct the labelling (P1^{′}, P2^{′}) by choosing for each v_{i} ∈ V_{i}, a label uniformly at random from P_{i}(v_{i}). If (v_{1}, v_{2}) ∈ G′ then the probability that (P1^{′}(v_{1}), P2^{′}(v_{2})) is a matching pair of labels is ≥ \frac{1}{|P(v_{1})|}. Therefore the expected number of edges covered is

≥ ∑_{v_{1}∈V_{1}} \frac{degree_{G′}(v_{1})}{|P(v_{1})|}

which, by a standard argument about convex functions is

≥ ∑_{v_{1}∈V_{1}} \frac{degree_{G}(v_{1})}{2 · 2^{k(n)} · |V_{1}|} = \frac{|E|}{2 · 2^{k(n)} · |V_{1}|}

since each v_{1} has the same degree.

Finally, there must exist a (P1^{′}, P2^{′}) that covers at least as many edges as the above expectation. Thus, there exists a labelling that uses only 1 label per vertex and covers more than a fraction 2^{−k(n)} of the edges, which is a contradiction. Hence any labelling has ℓ_{1}- cost > 2^{k(n)} · |V_{1}|. Finally, a labelling of this ℓ_{1}-cost must assign at least 2^{k(n)} labels to some vertex in V_{1}, which means that the l_{∞}-cost is ≥ 2^{k(n)}.

To finish the proof of Lemma 8, we notice that the size of the label-cover instance N, is 2^{(k(n))^{2} log^{3} n}. The gap between the costs of the label-cover in the two cases is 2^{k(n)}. Hence choosing k(n) = log^{\frac{3}{4ϵ}} n yields the desired gap of 2^{log^{0.5−ϵ} N}.

5.4 A 2-Prover, 1-Round Proof Protocol for SAT

The proof of Lemma 9 relies on the properties of a specific 2-Prover, 1-Round Proof Protocol for 3SAT. To ease the exposition, we will develop this protocol in stages by describing three different proof protocols, PP1, PP2 and PP3.

PP1:

[AL+] show that there is some constant 0 < b < 1, such that for any 3SAT formula, φ, there is a “robust” formula, φ′, constructable in polynomial time, such that:

• φ is satisfiable if and only if φ′ is satisfiable.

• If φ′ is not satisfiable then, any truth assignment satisfies at most a b fraction of its clauses.

The PP1 protocol proceeds as follows on input φ, which we assume is robust. The verifier, V, selects a clause, c, at random from φ for prover P_{1}, and a variable, x, at random from c, for prover P_{2}. Prover P_{1} returns a truth assignment for the variables occurring in c. Prover P_{2} returns a truth assignment for x. The verifier, V, accepts if the truth assignments are consistent (agree on x) and satisfy the clause, c. Notice that prover P_{2} is asked for a single truth value, thus its strategy corresponds to a truth assignment.

If φ is satisfiable then the provers can convince the verifier to accept by answering according to the same satisfying assignment, e.g. the first in lexicographic order. If φ is not satisfiable, the truth assignment according to which prover P_{2} answers can satisfy at most a b fraction of clauses. Thus, the verifier will reject with probability at least \frac{1−b}{3}.

PP2: Assume each query in the PP1 protocol is d = O(log(n)) bits long (padding as necessary). Let Q be the set of queries of PP1, and let Q_{i} be the the queries of prover P_{i}, i = 1, 2. Next let b_{i} ∈ {0, 1}^{d} denote the string with an 1 in the i-th position and 0’s elsewhere. Let B = {b_{i}|i = 1, …, d}.

The verifier, V, in PP2 will select a query at random from the set:

Q ∪ Q_{1} × B ∪ B × Q_{2} ∪ B × B

This may not seem like a very useful strategy for the verifier. We delay discussing the motivation to the next sectionwhere we describe the geometric properties of the protocol. In this section we simply analyze the error performance.

If the verifier, V, chooses a query which is not in Q, it accepts regardless of the provers’ responses. When V chooses a query in Q, it follows the PP1 protocol. With probability \frac{1}{d}, the verifier will choose a query from Q and, therefore, will reject an unsatisfiable formula with probability at least \frac{1−b}{3d)}.

To reduce the errror to 2^{−2k(n)}, the verifier, V, repeats the protocol m/2 in parallel (i.e. with m different provers), where m = O(k(n)d).

PP3: Next we’ll use the technique of [FL] to parallelize the PP2 protocol.

Let F be a finite field, |F | ≥ 2^{O(k(n))}. (Here we assume k(n) = poly(log(n))). For any input φ, and fixed strategy of the m provers, let p_{i} : F^{d} → F be the unique multilinear function in d variables such that for any q ∈ {0, 1}^{d}, p_{i}(q) is the answer provided by prover i on query q.

The verifier, V, will simulate the verifier of PP2 and construct queries for each of the m provers, q_{1}, …, q_{m}. Note that each q_{i} can be viewed as a point in F^{d}. Next, for each i, the verifier, V, chooses a random line, l_{i}, in F^{d} that passes through the point q_{i}. These m lines are provided to prover P_{1}. The verifier also selects a random point, t_{i}, on each line, l_{i}, and sends them to prover P_{2}.

Prover P_{1} returns m degree-d polynomials which are supposed to represent, for each i, the function p_{i} parameterized along the line l_{i}. Prover P_{2} responds with m values from F which are supposed to represent, for each i, the function p_{i} evaluated at the point t_{i}.

The verifier, V, computes the value of each of the i polynomials at the query points, q_{i}, and checks that these answers would have been accepted by the verifier in PP2. V also checks that the value of the ith polynomial at the random point t_{i} agrees with the value provided by prover P_{2}. If all of these checks pass, the verifier accepts.

If φ is satisfiable, then there is a winning strategy for the m provers of the PP2 protocol. Thus, the PP3 provers can convince the verifier to accept with probability 1. It is shown, in [FL] that when φ is not satisfiable, no provers can convince the verifier to accept with probability greater than 2^{−k(n)}.

5.5 Hardness of Pseudo-Covers

The proof of Lemma 9 follows from the next claim.

→

we should say how it follows

Claim: Let OPT be the minimum ℓ_{∞}-cost of a labelling that covers half of the edges. Then the minimum ℓ_{∞}-cost of a pseudo-cover is min \{\sqrt{|F |}, OPT\}. The proof of the Claim combines Lemmas 14, 15. The intuition is as follows. If, in any pseudo-cover, a v_{1} ∈ V_{1} node has a “large” fraction of cancelled edges then the cost of the pseudo-cover will be at least \sqrt{|F |}. On the other had, if no node has a “large” fraction of cancelled edges, then at least \frac{1}{2} of edges must be covered. In this case, cost of the pseudo-cover will be at least OPT.

Lemma 14 A pseudo-cover of l_{∞}-cost at most \sqrt{|F |} cancels at most \frac{d}{\sqrt{|F |}} fraction of the edges incident to

any vertex in V_{1}.

Proof: Let p̂ = (p_{1}(x_{1}), …, p_{m}(x_{m})) be a label in A_{1} that is assigned by a pseudo-cover to a node q_{1}. If the edge, e = (q_{1}[r], q_{2}[r]), incident to q_{1} is cancelled by the labelling then there must be a distinct label, p̂′ = (p′_{1}(x_{1}), …, p′_{m}(x_{m})), assigned to q_{1} such that p̂′(q_{2}[r]) = p̂(q_{2}[r]); i.e. these m-tuples of polynomials agree on the m-tuple of points p_{2}[r]. But p̂′(x) and p̂(x) are distinct m-tuples of polynomials of degree at most d and thus agree at no more than d/|F | fraction of the points in F^{m}. Consequently, two labels can cancel at most a d/|F | fraction of edges incident to q_{1} and \sqrt{|F |} are necessary to cancel a d/\sqrt{|F |} fraction.

Lemma 15 (An Expansion Lemma) A pseudo-cover that cancels at most a \frac{d}{\sqrt{|F |}} fraction of the edges at

any vertex in V_{1} must cover at least \frac{1}{2} of the edges.

Proof: Intuitively, we are going to prove something about the expansion properties of the graph obtained in the label cover eduction. To see why this is useful, let us fix a pseudo-cover that canels at most an α = \frac{d}{\sqrt{F}} fraction of edges of any v_{1} node. Notice, if no edge is cancelled, then the pseudo-cover is a total cover and its cost is at least OPT. So we may assume there is a cancelled edge and some v_{1} ∈ V_{1} is assigned a label. Then every edge incident to v_{1} that is not cancelled (and only an α fraction can be cancelled) must be covered. Suppose v_{2} ∈ V_{2} is adjacent to v_{1} by a covered edge. Then v_{2} must be assigned a label. Moreover, each of its edges must be covered so more v_{1} nodes must be assigned labels, etc. The graph obtained in the label cover reduction has certain expansion properties which guarantee that many edges must be covered.

This intuition is formalized in the following lemma. Here we let B be the set of V_{2} nodes that are not

assigned labels. Note that if v_{1} ∈ V_{1} is adjacent to a node in V_{2} \ B, it must be assigned a label. Further, at most an α fraction of its edges can be incident to B.

Lemma 16 Let B be a proper subset of V_{2} s.t. every vertex v_{1} ∈ V_{1} either has all its neighbors in B or at most an α fraction of its neighbors in B. Then ≥ (1 − β) fraction of the vertices in V_{1} has a neighbor in V_{2} \ B, where β = m/ |F | + 2(d − 1)α.

This Lemma relies on geometric properties of PP3 protocol for 3SAT. It is restated in geometric terms and proven in ??.

Lemma 16 implies that at most (1 − β)(1 − α) edges must be covered by any pseudo-cover that cancels at most an α fraction of edges of any V_{1} node. Lemma 15 follows by letting α = \frac{d}{\sqrt{F}}. (Recall that d = O(log(n)), m = O(k(n) log^{2}(n)), |F | = 2^{O(k(n))} and k(n) = poly(log(n).)

5.6 Proof of the Expansion Lemma

5.6.1 A Geometric View of PP3

Let W_{0} = AG(d, q) be the d-dimensional affine geometry over F = GF (q). Elements of W_{0} are called points. A line in W_{0} is a 1-dimensional affine subspace. Let W be the space W_{1} × ⋯ × W_{m} where W_{i} ≅ W_{0}. Elements of W are called Points. A Line is an ordered m-tuple of lines. Thus a Line has |F |^{m} Points. In general, an n-Hyperplane will be an ordered m-tuple of n-dimensional hyperplanes.

The geometric structure of the PP3 protocol is as follows. There is a set S of Points that are special for the verifier (these correspond to the questions picked uniformly at random in the PP2 protocol). A Lines that contain a special Point will be called special Line.

The queries, Q_{1}, to prover P_{1} are exactly the special Lines. The queries, Q_{2}, to prover P_{1} are exactly the Points.

The set of random seeds is R =

{(q_{1}, q_{2}) : q_{1} is a special Line containing the Point q_{2}}

In the graph obtained in the reduction to Label Cover, the V_{1} and V_{2} nodes correspond respectively to special Lines and Points. Notice, connection in this graph corresponds to incidence in the affine space.

We say that N ⊆ W_{i} is full-dimensional if it contains an affine base of W_{i}. A set N = ∏_{i} N_{i} where N_{i} ⊆ W_{i} is called a box of W. The box N is said to be Full-Dimensional in W if each N_{i} is full-dimensional in the corresponding W_{i}. Finally, a set S ⊆ W Totally Full-Dimensional if for every s ∈ S there is some Full-Dimensional box T ⊆ S such that s ∈ T.

Lemma 17 The special Points of the PP3 protocol are Totally Full-Dimensional.

The proof is obvious.

5.6.2 A Geometric Lemma

Now we restate Lemma 16 to make the geometry clear.

Let the Points of W be colored white and blue. We’ll say a Line is all-blue if every Point on it is blue.

Lemma 18 Let S ⊂ W be a set of special Points that is Totally Full-Dimensional. Suppose every special Line is either all-blue or has at most an α fraction of blue points. Then if there is at least one white Point, it must be the case that at least a (1−β) fraction of the special Lines must have a white Point, where

The proof of the lemma is easier to understood when m = 1. In this case, W = W_{0} so Points are points, Lines are lines and Hyperplanes are hyperplanes. Further, the condition that S is Totally Full-Dimensional is equivalent to requiring that S contain an affine basis of W. We will first prove the lemma when m = 1 and then generalize the result.

5.6.3 Proof of the Geometric Lemma: m = 1

Proof of Lemma 18: m = 1

Let B be the set of blue points. Assume that less than a (1 − β)-fraction of special Lines have a white Point. We’ll show that B = W.

There must be a Point u ∈ S such that the proportion of all-blue Lines through u is at least β. Let x ≠ u be a Point in W. Now S contains an affine basis of W, so it contains an affine basis of a Hyperplane U that includes u but not x.

Call a Line very special if it passes through u but not through any other Point of U. Then the proportion of all-blue lines among the very special Lines is at least β − m/ |F | = 2(d − 1)α.

By the following Sublemma, W \ U ⊆ B. But the point x was arbitrary. Thus W \ {u} ⊆ B. But every Line through u must be all-blue, thus u ∈ B.

Sublemma. Assume S contains an affine basis of a Hyperplane U of W and u ∈ U. Assume further that the proportion of all-blue Lines among the very special Lines is greater than 2(d − 1)α. Then B ⊇ W \ U.

The proof follows by induction on d. When d = 1 the Space is a single Line and the claim hold.

Now assume d ≥ 2. Let V be a Hyperplane of U and let s ∈ S ∩ U such that s ∉ V. An example for the case when d = 3 is shown in Figure 1; i.e. U is a Line and V is a Point. ^{→}

ADD FIGURE

Let Q be the set of Hyperplanes that contain V (one of these is U). Then the sets Q \ V, where Q ∈ Q, partition W \ V. On the other hand, a refinement of this partition is provided by the sets λ ∩ (W \ V) for Lines λ joining u to points in W \ V.

Call a Q ∈ Q almost-blue if Q \ V ⊆ B. Note that by the inductive hypothesis, if Q ∈ Q is not almostblue then the proportion of all-blue Lines among the very special Lines in Q is ≤ 2(d − 2)α.

Let η denote the proportion of almost-blue Hyperplanes in Q. If η ≤ 2α, then the proportion of all-blue Lines among the very special lines is ≤ 2(d−2)α+2α = 2(d − 1)α, contradicting the assumption in the Sublemma. Thus η > 2α.

Let now y ∈ W \U and consider the (unique) Line λ joining y to s. Each Q ∈ Q intersects λ in exactly one point; therefore more than a 2α fraction of λ ∩ W \ U is blue. But more than 1 − m/ |F | fraction of λ lies in W \ U; so at least a (1 − m/ |F |)2α > α fraction of λ is blue. Consequently λ is all-blue; in particular, x ∈ B.

5.6.4 Proof of the Geometric Lemma: m > 1

To prove the result for general m we want, simply, to carry out the previous proof in parallel in each of the m dimensions.

As before, there is a Point u = (u_{1}, …, u_{m}) ∈ S, (where u_{i} ∈ W_{i}) such that the proportion of all-blue Lines through u is at least β. Let x = (x_{1}, …, x_{m}) ≠ u be a Point in W. Now S is Totally Full Dimensional, so it contains a Full-Dimensional Box, T = ∏ T_{i} containing u; in other words, for each i, T_{i} is an affine basis for W_{i} and u_{i} ∈ T_{i}. Then clearly, for each i there is a T′_{i} ⊂ T_{i} such that u_{i} ∈ T′_{i}, T′_{i} is the affine basis of a hyperplane U_{i}, and ∏ T′_{i} ⊆ T ⊆ S. Therefore, S contains a Full Dimensional box of the Hyperplane U = ∏ U_{i} and u ∈ U.

The proof follows exactly as before from the generalized sublemma.

General Sublemma. Assume S contains a Full-Dimensional box of a Hyperplane U of W and u ∈ U. Assume further that the proportion of all-blue Lines among the very special Lines is greater than 2(d−1)α. Then B ⊇ W \ U.

The proof, again, follows by induction on d. When d = 1 the Space is a single Line and the claim hold.

Now assume d ≥ 2. Since S contains a Full Dimensional Box of U, we can find a Hyperplane V of U that contains u and a Point s ∈ S ∩ U such that s ∉ V. (Using the same kind of argument as used above.)

The remainder of the proof is identical to the case for m = 1.

6 Hardness of MAX-SATISFY

We now prove Theorem 3. Proof: We first show that approximating the problem within a factor (1 + ϵ) is NP-hard, and then show how to boost the gap of (1 + ϵ) to LARGE factors.

We use the following result, a joint consequence of a theorem of Arora et. al. [AL+] and a reduction due to [PY]. A vertex cover in a graph G = (V, E) is a set V′ ⊆ V such that for every edge {u, v}, either u ∈ V′ or v ∈ V′. Let V C_{min} be the size of the smallest vertex cover.

Theorem 19 There exists fixed constants c, ϵ and a polynomial time reduction from a SAT instance φ to a graph with n vertices, m = O(n) edges and degree 5, such that if φ is satisfiable then V C_{min} = cn, and if φ is not satisfiable then V C_{min} ≥ (1 + ϵ)cn.

We will reduce the vertex cover instance to a system of N = n + 3m linear equations, of which at most 2m + n − V C_{min} can be simultaneously satisfiable. This implies a gap of Θ(N) in the optimum in the two cases, since m = O(n).

For each vertex i we’ll construct a variable x_{i} and an equation x_{i} = 0. For each edge, {i, j}, we’ll construct 3 equations:

x_{i} + x_{j} = 1
x_{i} = 1
x_{j} = 1

Notice, at most 2 of the 3 equations for each edge can be satisfied simultaneously. Further, to satisfy 2 of these equations, x_{i} and x_{j} must take on values from {0, 1} and at least one must take the value 1.

We claim that the maximum number of equations are satisfied when all the x_{i}’s are 0/1. Suppose, under some assignment, x_{i} is not 0/1. We can strictly increase the number of equations satified by resetting the value of x_{i} as follows: If x_{i} < \frac{1}{2} then set x_{i} = 0. If x_{i} ≥ \frac{1}{2} then set x_{i} = 1.

Now notice that under any optimal assignment, the set of vertices {i : x_{i} = 1} constitutes a vertex cover. If not, then there must be be an edge {i, j}, such that both x_{i} and x_{j} are 0. Thus all three equations associated with this edge are unsatisfied. Resetting x_{i} to 1 will satisfy 2 equations associated with this edge, and violate one equation, x_{i} = 0, which was previously satisfied. Thus there is a a net gain of 1 equation satisfied, which contradicts the optimality of the original assignment. It follows that the optimum assignment satisfies 2m + n − V C_{min} equations.

Boosting the Gap to LARGE factors. We have N equations, in which the answer to MAX-SATISFY is either OPT or OPT·(1 − δ) for some δ > 0. Let the equations be written as p_{1} = 0, p_{2} = 0, …, p_{N} = 0. Let k, T be integers (to be specified later). The new set of equations contains, for every k-tuple of old equations, p_{i_{1}}, …, p_{i_{k}}, a set of T equations ∑_{j=1}^{k} p_{i_{j}}y^{j} = 0, where y = 1, 2, …, T.

Using the fact that a polynomial of degree k has at most k+1 roots, it is easily seen that then the number of equations that can be satisfied in the two cases is either ≥ \binom{OP T}{k} · T or ≤ \binom{M}{k} · k + \binom{OP T (1−δ)}{k} · T. Now choose T large enough to get a gap of approximately (1 − δ)^{k}.

→ This reduction gives systems of size \binom{M}{k}, which

correction here

is polynomial in M only for k a constant. To get a gap of N^{a}, while retaining the polynomial size, we resort to well-known techniques involving pseudorandom distributions. Consider a set of N^{O(1)} tuples in {y_{1}, …, y_{N}}^{k}, such that for every 0/1 assignment to {y_{1}, …, y_{N}} that assigns 1 to ρN variables, the fraction of all-1 tuples in our set is > sth, and for an assignment that assigns 1 to ρ(1 − ϵ)N variables, the fraction of all-1 tuples in our set is < sth′. When we use such sets in our reduction instead of the set of all possible k-tuples of equations, we get the desired result.

7 Improved LARGE factors

In this section we give a proof of the following

Theorem 20 Assume there are polynomial time algorithms that approximate any of the following problems within a factor of 2^{log^{1−ϵ} n} for any ϵ > 0: (i) NV_{p}, for p ≥ 1 (ii) NEAREST CODEWORD (iii) MIN UN-SATISFY , then NP ⊆ Dtime(n^{poly(log n)}).

Our proof will be based on an iterative construction which starts from instances with a (fixed) constant gap and gradually increases the gap. We will use the setting of lattices in order to describe the method and we will further restrict ourselves to the case p = 1. Hardness results for the other problems will follow by suitable modifications as indicated in the previous section.

We have just shown that one could transform an instance ϕ of SAT into an instance of SV_{1} consisting of a lattice L(b_{1}, ⋯, b_{m}) together with a vector b_{0} and an integer K such that, for some constant c > 1 the following statements hold:

i) if ϕ is satisfiable then the minimum distance of L to b_{0} under the ℓ_{1}-norm is K ii) if ϕ is not satisfiable then the minimum distance of L to b_{0} under the ℓ_{1}-norm is ≥ cK.

We have also shown how to modify our basic reduction in order to deal with the NV_{1} problem with 0/1 vectors. The instances we built for this specific problem actually enjoy some further properties that we will need: iii) if ϕ is satisfiable, then there is a vector v achieving minimum distance to b_{0}, with all coordinates 0 or 1 iv) if ϕ is not satisfiable then, for any non zero integer α and any vector w of the lattice, αb_{0} + w has at least cK non zero coordinates.

In order to prove theorem 20, we will build a polynomial-time reduction which transforms instances of NV_{1} enjoying the above properties into instances enjoying similar properties with c replaced by c^{2}. Iterating a large number of times will then yield the result.

We start from the matrix M whose rows are the vectors b_{1}, ⋯, b_{m} generating the lattice L(b_{1}, ⋯, b_{m}), considered above. M has m rows and say p columns. We let M̃ be the (m, p^{2}) matrix obtained from M by replacing each coefficient μ by a block of p coordinates exactly equal to the row vector μb_{0}. The new lattice is generated by the rows of a matrix of the following form

M′ =

(  M̃ ; \overline{M}  )

where \overline{M} is built as follows:

\overline{M} =

(  \begin{matrix}P_{1} & ⋯ & 0 & 0 \\ 0 & P_{2} & ⋯ & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & ⋯ & P_{p} \end{matrix}  )

In the above diagram, each matrix P_{k} has m rows and p columns and is simply a copy of M. Thus, we have built a matrix M′ with m(p + 1) rows and p^{2} columns through a construction that can clearly be achieved in polynomial time. Finally, we consider the lattice L′ generated by the rows of M′ and the vector b′_{0} obtained from b_{0} by replacing each coefficient μ by a block of p coordinates exactly equal to the row vector μb_{0}. We also set K′ = K^{2}. We then make the following remarks:

1. If ϕ (the given instance of SAT) is satisfiable, then there is a lattice vector w built as a linear combination of the first m rows of M′ such that b′_{0} + w has exactly K non-zero blocks, each consisting of a copy of the row vector b_{0}. In each of these blocks, coordinates can be further cancelled by using the corresponding matrix P_{k} so as to leave exactly K ones. Thus, the distance of b′_{0} to L′ is exactly K^{2}. This proves properties i and iii for L′, b′_{0}, K′ with c replaced by c^{2}.

2. If Φ is not satisfiable, then any vector w built as a linear combination of the first m rows of M′ will leave at least cK non-zero blocks in b′_{0} + w. In each of these blocks, use of the corresponding matrix will cancel more coordinates but, using property iv of the pair L′, b′_{0}, we can see that at least cK non zero coordinates are left. Therefore the distance of b′_{0} to L′ is at least (cK)^{2}. The same argument holds with b′_{0} replaced by αb′_{0}, thus showing properties ii and and iv for L′, b′_{0}, K′.

Thus, as announced, we have built a reduction with c replaced by c^{2}. We now turn to the proof of theorem 20. This proof is based on repeating the above construction k(n) times, where k(n) is a function of the size n of the original SAT instance we started with. During this iterative construction, the size of the matrix used to define the lattice grows: the number of columns reaches p^{2^{k(n)}} and the number of rows m ∏_{i=0}^{k(n)}(p^{2^{i}} +1), which is bounded by m(1+p)^{2^{k(n)}+1}. In any case, the construction cannot be achieved in time polynomial in n but rather in time n^{O(2^{k(n)})}. If we let 2^{k(n)} be equal to log^{β} n, then the construction is in Dtime(n^{poly(log n)}) and the size of the resulting lattice is N = n^{O(log^{β} n)} = 2^{O(log^{β+1} n)}. Note that log N = O(log^{β+1} n). Also, the gap for the resulting instances of NV_{1} has become c^{2^{k(n)}} = c^{log^{β} n} =

2^{O((log N)^{\frac{β}{β+1}} )}.

Assume that some polynomial time algorithm approximates the problem NV_{1} within a factor 2^{log^{1−ϵ} n} for any ϵ < 1 − \frac{β}{β+1} then, applying this algorithm to the output of the above iterated construction, one can decide the satisfiability problem for a given instance ϕ of SAT. Since our construction is in Dtime(n^{poly(log n)}) the resulting decision algorithm is in Dtime(n^{poly(log n)}) as well. This finishes the proof of theorem 20.

8 Open Problems

As mentioned earlier, hardness for NV_{p} or SV_{∞} within a factor of \sqrt{dim} would prove the hardness of SVP_{2}, which is a major open problem. It seems that the best conceivable factor achievable using interactive proofs/PCP may be n^{c} for some small c > 0. But we feel that the geometric construction used in our reduction to SV_{∞}might be indicative of the nature of relevant techniques.

A related open problem is to improve our results by proving the problems NP-hard rather than almost-NP-hard. More efficient 2-prover, 1-round interactive proofs for NP (as conjectured in [BG+]), or a direct reduction from [AL+] might help.

Acknowledgements

Thanks to Madhu Sudan for suggesting that techniques from interactive proofs might be helpful in proving the hardness of lattice vector problems, and to Ravi Kannan for his prompt responses to questions on lattices. We also thank Manuel Blum, Tomas Feder, Dick Karp, Mike Kearns, Mike Luby, Ron Rivest and Umesh Vazirani for helpful discussions.

References

[AL+] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. Proof verification and intractability of approximaion problems. 33rd FOCS, 1992, 13-22.

[AS] S. Arora, S. Safra. Probabilistic Checking of Proofs: A New Characterization of NP. 33rd FOCS, 1992, 2-13.

[Bab] L. Babai. On Lovász’s lattice reduction and the nearest lattice point problem. Combinatorica 6:1-14, 1986.

[BF+] L. Babai, L. Fortnow, L. Levin, M. Szegedy. Checking Computations in Polylogarithmic Time. Proc. ACM Symp. on Theory of Computing, 21-31, 1991.

[BFL] L. Babai, L. Fortnow, C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Comput. Complexity 1 (1991), 16-25.

[Bel] M. Bellare. Interactive Proofs and Approximation. IBM Res. Rep. RC 17969 (1992).

[BG+] M. Bellare, S. Goldwasser, C. Lund, A. Russell. Efficient Multi-Prover Interactive Proofs with Applications to Approximation Problems. 25th STOC, 1993, 113-131.

[BR] M. Bellare, P. Rogaway. The Complexity of Approximating Non-Linear Programs. IBM Research Report RC 17831 (March 1992).

[BMV] E. R. Berlekamp, R. J. Mc Eliece, H. C. A. Van Tilborg. On the inherent intractability of certain coding problems, Trans. Inform. Theory (1978) 384-386.

[BK] M. Blum, S. Kannan. Designing programs that check their work. 21st STOC, 86-97, 1989.

[BLR] M. Blum, M. Luby, R. Rubinfeld. Selftesting/correcting with applications to numerical problems. 22nd STOC, 73–83, 1990.

[Bol] B. Bollobás. Combinatorics. Cambridge Univ Press 1986.

[FG+] U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy. Approximating clique is almost NP-complete. 32nd FOCS, 2-12, 1991.

[FL] U. Feige, L. Lovász. Two-Prover One-Round Proof Systems: Their Power and Their Problems. 24th STOC, 733-741, 1992.

[FT] A. Frank, É. Tardos. An application of simultaneous approximation in combinatorial optimization. 26th FOCS, 1985, 459-463.

[GJ] M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the theory of NP-Completeness. W. H. Freeman, 1979.

[HS] K-U. Hoeffgen, H-U. Simon. Robust Trainability of Single Neurons. COLT’92, 428-439.

[JP] D. S. Johnson, F. P. Preparata. The Densest Hemisphere Problem. Theor. Comput. Sci. 6(1978), 93-107.

[K] R. Kannan. Minkowski’s convex body theorem and integer programming. In Mathematics of Operations Research, Vol 12, No. 3, 1987.

[Kar] R. M. Karp. Reducibility among combinatorial problems. Miller and Thatcher, eds., Complexity of Computer Computations, 85-103. Plenum Press, 1972.

[LLS] J. Lagarias, H.W. Lenstra, C.P. Schnorr. Korkine-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10 (1990), 333-348.

[LO] J.C. Lagarias and A.M. Odlyzko. Solving lowdensity subset-sum problems. J. ACM 32 (1985), 229-246.

[L^{3}] A.K. Lenstra, H.W. Lenstra, L. Lovász. Factoring Polynomials with rational coefficients. Math. Ann. 261 (1982), 513-534.

[Lov] L. Lovász. An Algorithmic Theory of Numbers, Graphs and Convexity. NSF-CBMS Reg. Conference Series. SIAM, 1986.

[LY] C. Lund, M. Yannakakis. On the Hardness of Approximating Minimization Problems. 25th STOC, 1993, 286-293.

[MP] M. Minsky, S. Papert. Perceptrons, 1968.

[Ni] N. Nisan. Pseudo-random Generators for Logspace Computation. 22nd STOC, 1990, 204-212.

[PY] C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes 20th STOC, 229-234, 1988.

[Sch] C.P. Schnorr. A hierarchy of polynomial-time basis reduction algorithms. Proc. Conf. on Algorithms , Pécs (Hungary), Lovász, Szemerédi, eds., North-Holland 1985, 375-386.

[S] J. Stern. Approximating the number of error locations is NP-complete. Proc AAECC-10, LNCS (1993), to appear.

[vEB] P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Rep. 81-04, Math. Inst. Univ. Amsterdam.

[Z] D. Zuckerman. NP-complete problems have a version that’s hard to approximate. 8th Structure in Complexity Theory Conf., 1993, 305-312.