PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

Irit Dinur^{∗}  Eldar Fischer^{∗}  Guy Kindler^{∗}  Ran Raz^{†}  Shmuel Safra^{∗}

Abstract

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be verified with a constant number of accesses, and with an error probability exponentially small in the number of bits accessed, where this number is as high as log^{β} n , for any constant β < 1. (The BGLR conjecture claims the same for any β ≤ 1).

Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables. That is, given a system of quadratic-equations over a field F (of size up to 2^{log^{β} n}), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a \frac{2}{|F|} fraction of them.

At the same time, our proof presents a direct construction of a low-degree-test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only relying on recursive applications of the entire PCP theorem.

Introduction

Each L ∈ NP is reducible to 3-SAT, by Cook-Levin’s characterization of NP. The reduction is a polynomial-time algorithm that accepts an input string I, and produces a set Ψ, of Boolean functions (local-tests), each depending on a constant number of variables, that are taken from some common set of variables. Ψ represents membership of I in L, in the sense that there exists an assignment satisfying all tests if and only if the input is in L.

A PCP characterization of NP differs from Cook’s in regards to what is guaranteed in case the input is not in L: In Cook’s characterization, one can only be sure that no assignment would satisfy all Ψ’s local-tests. In a PCP characterization of NP, in contrast, it is guaranteed that no assignment satisfies even a small fraction of them.

A satisfying assignment to Ψ can be viewed as a witness to I’s membership in L. According to the PCP characterization of NP, this witness can be verified by randomly picking one local-test of Ψ and checking whether it holds (hence the term PCP – Probabilistic Checking of Proofs). The error probability of a PCP characterization is a bound on the fraction of Ψ that can be satisfied in case the input is not in L.

For most applications of PCP, the characterization of NP with constant error-probability and variables of constant range [AS92, ALM^{+}92] suffices. In order to prove NPhardness of other problems, however, sub-constant errorprobability has turned out to be essential. For example [LY94] and [BGLR93] were able to prove approximating SET-COVER to within logarithmic factors almost NP-hard, using the constant error-probability PCP characterization of NP. To improve this result to strict NP-hardness,

[BGLR93] had suggested the ’sliding scale’ conjecture. The BGLR conjecture states that it is possible to keep

the number of variables accessed by each local-test constant while increasing the variables’ range, and to achieve error probability polynomially small in the size of the variables’ range. In other words, a membership-proof can be verified by accessing a constant number of words, such that the error probability is exponentially small in the length of a word.

One cannot expect the error-probability to be less than polynomially small in the size of the variables’ range, since a random assignment is expected to satisfy such a fraction, no matter what structure the local-tests take (recall that each test depends on a constant number of variables). Hence the BGLR conjecture is optimal in the sense of errorprobability.

According to the BGLR conjecture, the variables’ range may be up to polynomially large. It is unlikely to hold for variables’ range larger than polynomial, since the errorprobability would then become less than polynomially small in the size of Ψ, therefore in case the input is not in L, no local-test succeeds, making it easy to decide if the input is in L.

∗ School of Mathematical Sciences, Tel Aviv University, ISRAEL † Weizmann Inst. of Science , ISRAEL

The conjecture was eventually shown true for a sizeable portion of the applicable range-size in [RS97], which showed a PCP characterization of NP where the error-probability is exponentially small in the size of the variables, as long as the variable size is up to log^{β} n, for some positive constant β (see also [AS97]).

Our Main Results

In this paper, we improve the above result by increasing the range of β for which it holds, substituting “some constant” with “any constant smaller than 1”, thus coming closer to proving the BGLR conjecture for the full applicable range. Our results are, in fact, stronger: we show that given a system of quadratic-equations over a field F (|F| ≈ 2^{log^{β} n} for any constant β < 1), where each equation depends on a constant number of variables, it is NP-hard to decide whether there is a common solution to all of the equations, or if every assignment satisfies no more than a \frac{2}{|F|} fraction.

Our proof also gives a direct construction of a low-degree-test whose error-probability is exponentially small in the number of bits accessed, as discussed below.

Related Results

We note that no PCP result obtains an exponentially small error probability for a constant number of accesses and O(log n) number of bits in each access, even when allowing the reduction to be super-polynomial - here n denotes the size of the generated system. The repetition lemma of [Raz98] shows that by two accesses to O(log n) bits, the error-probability is exponentially small, but only in the size of the original input, while the size of the construction is n^{log n}. Similarly, the multi-linear extension of [BFL91] yields a system with a \frac{1}{n} error-probability but whose size is n^{log n}. In fact, in any known reduction there is always a factor of at least log^{ϵ} n in the exponent that separates the error-probability from the size of the generated instance.

Reaching an error-probability polynomially small in the size of the generated instance is an important open problem. Such a characterization of NP would improve hardness results for several problems. For example, approximating the ’Monotone-Minimum-Satisfying-Assignment’ problem (which is closely related to approximating the length of propositional proofs [ABMP98]) has been shown NP-hard in [DS98] via a reduction from PCP (such that the hardness of approximation ratio is preserved). Hence a polynomially small error-probability PCP characterization of NP would immediately imply that it is NP-hard to approximate the length of propositional proofs to within an n^{ϵ} factor for some constant ϵ > 0.

[RS97] managed to keep the exponential relation between the number of bits accessed and the error-probability, thus showing the BGLR conjecture true for variables’ rangesize of up to 2^{log^{β} n} for some constant β < 1. For larger β (any constant β < 1) [RS97] showed a system whose error probability is 2^{− log^{β} n}, yet without the exponential relation between the number of bits accessed and the errorprobability (the number of bits accessed was O(log^{β} n · poly log log n)). This factor of poly log log n is significant when viewing, for example, the result in terms of Gap-Quadratic-Solvability. The result of [RS97], if it were to be translated to Gap-Quadratic-Solvability terms, would at best give an equation system with each equation depending on O(poly log log n) variables. In comparison, our result translates to a quadratic equation-system with the same error-probability, but where every equation depends on a constant O( \frac{1}{1−β}) number of variables.

An essential component of the known proofs for PCP characterizations of NP, involves a consistency test for lowdegree-polynomials called low-degree-test. A low-degree-test of small error-probability seems necessary in order to show a PCP characterization of NP of small error-probability. Such low-degree-tests with small error-probability appeared in [RS97, AS97].

Technique

We use the general framework of [AS92, ALM^{+}92, RS97] for our proof, however replace the generalized form of the composition paradigm utilized in previous PCP proofs, by a more concrete representation. Our result could have been obtained using the previous structure, however this representation simplifies our proof, and some of the techniques may be of independent interest.

Our proof takes the form of a series of linear (degree preserving) transformations of quadratic equation-systems. All of these equation-systems are over the same field. These two ideas – namely fixing the field throughout the proof and utilizing linear transformations – combined, overcome the barrier the proof technique of [RS97] couldn’t, enabling the claimed NP-hardness of Gap-Quadratic-Solvability for a field of size 2^{log^{β} n}, for any constant β < 1, unlike some β < 1 in [RS97].

Instead of using recursive applications of the entire PCP theorem, we separate the proof into two parts. The first part consists of iterative applications of the sum-check technique. The second, low-degree-test part, shows a concrete representation of an LDF (LDF = low-degree function) and a direct low-degree-test whose error-probability is exponentially small in the number of bits accessed.

A low-degree-test of small (sub-constant) error-probability seems necessary in order to show a PCP characterization of NP of small (sub-constant) error-probability. Such lowdegree-tests with small error-probability appeared in [RS97, AS97]. [RS97] introduced a new low-degree-test (plane-vs.- plane) and showed it to be of small error-probability. The previously used line-vs.-point test was shown by [AS97] to be of small error-probability too.

The error probability of all these tests is still not exponentially small in the number of bits accessed. In fact, in any such direct low-degree-test comparing subspaces (lines, planes, etc.) for consistency, the error-probability can be no less than polynomially small in the number of bits accessed. One can attain exponentially small error-probability by utilizing the composition technique, applying the entire PCP theorem to the known low-degree-test. Our proof, in contrast, makes the recursion concrete, utilizing an explicit tree-like representation of LDFs, yielding a direct low-degree-test.

The proof employs two techniques to obtain such an explicit representation for an LDF. The first technique, called cube-representation (section 3.1), specifies how an LDF over a multi-dimensional space can be represented by its restrictions to cubes (affine subspaces of constant dimension). The second is a new technique, called embedding extension (section 3.2), which embeds an LDF over a space of constant dimension as a function of significantly lower degree over a space of higher dimension. The alternating application of the cube-representation and the embedding techniques enables a concrete representation of an LDF, thus eliminating the need for recursive application of the entire PCP theorem.

Gap-Quadratic-Solvability

Our theorem is in fact stronger than the PCP characterization claimed, imposing additional structure on the localtests, namely requiring the tests to be quadratic-equations over some finite field. We define the gap version of the Maximum Quadratic-Solvability problem as follows:

Definition 1 (Gap-Quadratic-Solvability) The gap-Quadratic-Solvability problem with parameters D, F and ϵ, denoted gap-QS[D, F, ϵ], is as follows. An instance of the problem is a set of n quadratic-equations over a finite field F = ℤ_{p} for a prime p, where each equation has at most D variables. The problem is to distinguish between the following two cases:

Yes. There is an assignment to the variables that satisfies all of the equations.

No. Every assignment to the variables satisfies at most an ϵ(n) fraction of the equations.

An instance which falls under one of the above criteria is said to have the gap property. Any outcome is acceptable for instances that do not have the gap property.

Our main theorem shows NP-hardness of gap-QS for a field of size |F| = 2^{c log^{β} n} for some constant c, and an error parameter ϵ = \frac{2}{|F|}. Note that the requirement for a \frac{2}{|F|} error is almost optimal, since it is easy to satisfy a \frac{1}{|F|} fraction of any system by a random assignment. On the other hand, from any error ϵ = \frac{1}{|F|^{c}} which is polynomially small in the size of the field, one can obtain a \frac{2}{|F|} error by a simple amplification technique.

We therefore abbreviate gap-QS[D, F] for the gap-QS problem where ϵ is fixed to be \frac{2}{|F|}. This error probability is polynomially small in the size of the field, and therefore exponentially small in the size of each variable (namely log |F|).

Theorem 1 (Main Theorem) For every constant β < 1 there exists a constant c > 0 such that gap-QS[O(1), F] is NP-hard, where |F| = 2^{c log^{β} n}.

This theorem holds (and obtained via the same techniques) for any field size |F| < 2^{log^{β} n}. In this paper, however, we focus only on the largest size.

Gap-QS[n, F], where the number of variables in each equation is not bounded, is proven NP-hard in [HPS93] for any polynomially bounded field size, using simple linear codes:

Theorem 2 ([HPS93]) Gap-QS[n, F] is NP-hard, for any polynomially bounded field size.

Hence the entire difference between Cook-Levin’s characterization of NP (from which theorem 2 follows) and the PCP characterization boils down to reducing the number of variables each equation accesses to constant. The proof commences with Ψ_{0} ∈ gap-QS[n, F] and by a series of degree preserving (linear) transformations arrives at Ψ_{l} ∈ gap-QS[O(1), F]. Ψ_{l} is an equation-system that enjoys the same gap in the fraction of satisfiable equations yet each of its equations accesses a constant number of variables. Namely either all of the equations are satisfiable or no more than a \frac{2}{|F|} fraction. An essential ingredient of our proof is that the field remains fixed throughout this series of transformations. Writing the size of F in terms of the size of Ψ_{l}, m, yields |F| = 2^{c log^{β} m} for some constant c as required by theorem 1, since m is polynomial in n.

Structure of the Reduction

The reduction is broken into two parts. The first part of the reduction, the sum-check part (summarized in lemma 1), transforms each equation of Ψ_{0} by a series of reductions, to many new equations, each of which accesses a constant number of encoding variables. These variables encode Ψ_{0}’s variables – as often done in proofs of PCP characterizations of NP – by their low-degree-extension (see definition 5). This means that the new set of encoding variables has one variable for each point in some geometric domain, and assignments are said to be legal encodings if these variables receive the point evaluation of some LDF (=low-degree-function, see definition 4) over the domain. The new equations interpolate the values of old variables by linear combinations of encoding variables, therefore the degree of the equation-system is maintained.

Given an assignment to the new variables which is a legal encoding, the ’sum-check’ simulates (with a small error) an equation depending on up to n variables by many equations, each accessing fewer variables. The sum-check part performs this ’simulation’ repeatedly, eventually arriving at a system of equations that each access a constant number of variables.

The resulting equation-system has certain subsets of variables designated each to some geometric domain, and whose values supposedly represent the low-degree extension (see definition 5) of the values assigned to variables of the old system. Assignments to the variables are considered legal encodings if they assign LDFs of a certain degree to these subsets. We prove that in the end of the sum-check part, every assignment that is a legal encoding either satisfies all of the equations or less than an ϵ fraction. The proof of lemma 1 relies mainly on previously known techniques, and is omitted due to space limitations.

The second part of the reduction, the low-degree-test part (section 3), is aimed at getting rid of the ’encoding’ assumption. It transforms the equation-system generated by the sum-check into an equation-system as in theorem 1. This goal is achieved by explicitly representing the LDFs in a way that allows checking consistency while keeping the number of variables in each equations constant (lemma 2). This representation is accomplished by alternately applying the cube-representation method, that appears in subsection 3.1, and the embedding extension, appearing in subsection 3.2.

The cube-representation technique allows the representation of LDFs over a multi-dimensional domain F^{d}, by their restriction to affine-subspaces of constant degree. We show that in such a representation, one can consistently read a value of a point, by reading it from a random affinesubspace (containing the point) and verifying the consistency of the affine subspace by comparing it with the global domain F^{d} on a random point.

The embedding extension is a new technique showing how to represent an LDF over a constant-dimensional space, by a significantly lower degree LDF over a higher dimensional space.

These two techniques, when alternately combined, repeatedly reduce the degree and the dimension of the representation, until eventually we obtain a representation of an LDF that enables consistent point evaluation by a constant number of accesses.

We begin in section 1, by giving preliminary notions and definitions. We then proceed in section 2 to show the reduction, based on lemma 1 and lemma 2. Section 3, as mentioned, contains the LDF tree-like representation.

1 Preliminaries

This separation is formalized by a mechanism called assumptions. Let Assign(𝒱) =^{def} {A | A : 𝒱 → F } be the set of possible assignments to the variables 𝒱 of an equationsystem Ψ. For any assignment A ∈ Assign(𝒱) we define the satisfiability of Ψ by A as

s(Ψ, A) =^{def} Pr_{ψ∈Ψ} [ψ is satisfied by A]

and the satisfiability of Ψ as

s(Ψ) =^{def} max_{A∈Assign(𝒱)} [s(Ψ, A)]

The initial and final systems Ψ_{0} and Ψ_{l} are a special kind of promise problems, namely gap problems. The promise over them is that either the equation-system is totally satisfiable, or no more than ϵ-satisfiable – s(Ψ_{0}), s(Ψ_{l}) ∉ (ϵ, 1). Ψ_{l} is obtained from Ψ_{0} by a series of transformations Ψ_{0} ⇒ Ψ_{1} ⇒ … ⇒ Ψ_{l}. The intermediate systems Ψ_{i} are also promise problems, nevertheless, the structure of their promise is more complex than the fractional gap.

Each equation-system Ψ_{i+1} is obtained from Ψ_{i} by encoding Ψ_{i}’s variables into new variables and then having Ψ_{i+1}’s equations access these new variables. For each assignment A to Ψ_{i}’s variables there is an assignment A′ to Ψ_{i+1}’s variables that encodes it - A′ is called a legal encoding of A. If we were sure Ψ_{i+1} is only assigned legal encodings we could maintain the gap. The gap of the equation system now becomes more complex, namely, either there is an assignment satisfying all of the equations, or (and this is the more complex part) every assignment to the variables – such that the values on the new variables form a legal encoding – cannot satisfy more than ϵ of the equations. In case Ψ_{i} is totally satisfiable by an assignment A, then its encoding A′ totally satisfies Ψ_{i+1}. This means that we know that in the ’yes’ case, the system is totally satisfiable by a legal encoding.

Assumptions

The promise described above guarantees that the equationsystem Ψ falls into one of the following two cases,

Yes. There is an assignment satisfying all of the equations in Ψ, and such that the assignment to certain designated variables is from a restricted set of ’legal assignments’.

No. No legal assignment can satisfy more than an ϵ fraction of Ψ.

Let A_{yes} ⊆ Assign(𝒱) be a set of assignments for Ψ (corresponding to legal encodings of assignments to the previous system). When we reduce Ψ to a system Ψ′, we show how an assignment in A_{yes} can be encoded as a legal assignment of Ψ′. Sometimes, however, a legal assignment for Ψ′ cannot be decoded back to a legal assignment for Ψ, but only to an assignment which is ’very close’ to being legal. Let A_{no} ⊃ A_{yes} be a possibly larger set of assignments (containing decodings of legal assignments of the previous system). An assumption over 𝒱 is defined as a pair (A_{yes}, A_{no}) of arbitrary subsets A_{yes} ⊆ A_{no} ⊆ Assign(𝒱). We define a gap-under-assumption as follows,

Definition 2 ((ϵ, 1)-Gap Under Assumption) Let Ψ be an equation-system over a variable set 𝒱, and let (A_{yes}, A_{no}) be an assumption for Ψ. Ψ is said to have an (ϵ, 1)-gap under the assumption (A_{yes}, A_{no}) if exactly one of the following holds:

Yes. There exists an assignment A to 𝒱, A ∈ A_{yes}, that satisfies Ψ.

No. Every assignment A to 𝒱, A ∈ A_{no}, satisfies no more than an ϵ fraction of Ψ.

In other words, if we generalize the satisfiability function for restricted subsets of assignments by

s_{A}(Ψ) =^{def} max_{A∈A}(s(Ψ, A))

then a gap-under-assumption is a stronger promise on Ψ, stating that in the yes case s_{A_{yes}}(Ψ) = 1 rather than s(Ψ) = 1, and in the no case s_{A_{no}}(Ψ) ≤ ϵ rather than s(Ψ) ≤ ϵ.

Let us go back to the series of reductions of equationsystems, Ψ_{0} ⇒ Ψ_{1} ⇒ ⋯ ⇒ Ψ_{l}. In each reduction the variables 𝒱_{i} of Ψ_{i} are encoded by the variables 𝒱_{i+1} of Ψ_{i+1}. We will need to show that the gap is maintained by the reduction. The easy part will always be to show how a legal assignment that totally satisfies Ψ_{i} can be encoded into a totally satisfying assignment for Ψ_{i+1}. The harder part will be to show that any assignment for Ψ_{i+1} can be ’decoded-back’ into an assignment satisfying roughly the same fraction of Ψ_{i}. This is the counter-positive way of saying that no-instances are mapped into no-instances.

Definition 3 (Gap-Maintaining Reduction) Let E_{1} and E_{2} be two sets of equation-systems, and let R be a polynomial algorithm that on input Ψ ∈ E_{1} outputs an equationsystem Ψ′ ∈ E_{2}.

For a system Ψ ∈ E_{1}, we denote its assumption by A = (A_{yes}, A_{no}), and denote the assumption of the system R generates from Ψ, Ψ′, by A′ = (A′_{yes}, A′_{no}). R is said to be a gap-maintaining reduction between E_{1} and E_{2} if there exists a constant c > 0 such that Ψ and Ψ′ are assured to have the following properties:

1. If (s_{A_{yes}}(Ψ) = 1) then also (s_{A′}_{yes}(Ψ′) = 1).

2. For any assignment A′ ∈ A′_{no} there exists an assignment A ∈ A_{no} that satisfies almost the same fraction of equations, i.e. s(Ψ, A) ≥ s(Ψ′, A′) − |F|^{−c}

In that case we write Ψ⇒Ψ′, meaning that (1) and (2) hold for Ψ and Ψ′. If there exists a gap-maintaining reduction between E_{1} and E_{2}, we write E_{1} ⇒ E_{2}

If Ψ_{i+1} is generated from Ψ_{i} by a gap-maintaining reduction, by property 1 the gap is indeed maintained - if Ψ_{i} is satisfiable then so is Ψ_{i+1}. On the other hand, if it is not even ϵ satisfiable then Ψ_{i+1} is at most ϵ + |F|^{−c} satisfiable, by property 2 in the definition (we later take care of the additional |F|^{−c}).

During the first half of the construction (the sum-check part), we repeatedly reduce an equation-system Ψ with a gap under assumption to a new equation-system by adding to its variables 𝒱 new variables 𝒱′ that serve as some encoding of the old variables. We then prove that the new system has a gap under the old assumption (A_{yes}, A_{no}) (that only restricts the assignments to 𝒱) and under a new assumption (A′_{yes}, A′_{no}) over the new variables 𝒱′. In other words, the assumption of the new system will be the intersection of the old and the new assumptions,

(A_{yes}, A_{no}) ∩ (A′_{yes}, A′_{no}) =^{def} (A_{yes} ∩ A′_{yes}, A_{no} ∩ A′_{no})

When we say that an equation system has a gap under several assumptions, it is implied that the system has a gap under the intersection of the assumptions.

Encodings and Extensions

In each step of our series of reductions, we generate a new system from an old one by extending some subsets of the variables, such that the extended variables encode the old ones. In the intermediate steps of the reduction, we set assumptions allowing only assignments that are legal encodings over the extensions. The most frequently used extension technique is the low-degree extension which extends assignments via low-degree functions. An additional type of extension, called the multiplicative-extension, is used exactly once in the proof.

Low–Degree Extension

Before going into the definition of LDF extension, let us first define an LDF formally,

Definition 4 (Low Degree Function - LDF) A function f : F^{d} → F is said to have degree r, and called an [r, d]-LDF, if its values are the point evaluation of an r degree polynomial on F^{d}.

A Low-Degree extension of a set 𝒱 of variables, is done by identifying each variable with a point in F^{d}, and then assigning new variables for the rest of the points in F^{d}. An assignment is now viewed as a function from F^{d} to F. The assignment of 𝒱 can then be encoded as an LDF over the extended set.

Definition 5 (Low-Degree Extension) Let h < |F|^{\frac{1}{2}} , and define H = {0, 1, …, h} ⊆ F. Let 𝒱 be an arbitrary set of variables, and take d =^{def} log_{h+1}(|𝒱|). ^{1} Identify every point x ∈ H^{d} with a distinct arbitrary variable 𝒱[x].

Now add a new variable 𝒱[x], for each point x ∈ F^{d} \ H^{d}. The extended set of variables 𝒱̂ =^{def} {𝒱[x] | x ∈ F^{d} }, together with the identification x → 𝒱[x], is called the lowdegree extension of 𝒱 with parameter h.

Given an arbitrary assignment A : 𝒱 → F, we say that the assignment Â: 𝒱̂ → F is a proper-extension of A of degree r if Â coincides with A, and also the correspondence x → Â(𝒱[x]) is an [r, d]-LDF.

To ensure that the extended variable set is assigned a legal encoding, we introduce an LDF-assumption over it.

Definition 6 (LDF-Assumption) Let r_{yes} ≤ r_{no} ≪ |F|. Let D be a variable set, containing a distinct variable D[x] for each x ∈ F^{d}. The assumption (A_{yes}, A_{no}) defined by

A_{yes} = {A |The mapping x → A[D[x]]is an

[r_{yes}, d] − LDF on F^{d}}

A_{no} = {A |The mapping x → A[D[x]]is an

[r_{no}, d] − LDF on F^{d}}

is called an [r_{yes}, r_{no}, d]-LDF-assumption over D, and denoted by L_{D}[r_{yes}, r_{no}, d]. D is called the domain of the assumption, or its assumption-domain (the assumption only restricts the assignments to the variables in its domain).

LDF-assumptions can be joined by intersection, like every assumption. However, we will only join LDF-assumptions over pairwise disjoint domains, so a variable will belong to the domain of at most one LDF-assumption. The reason for this is that we will need, at a later stage of the proof, to get rid of these assumptions - and we do it by adding variables to the equations that verify them. If a variable were to participate in many LDF-assumptions, it would over-increase the number of variables in the equations of the final equation-system.

If D_{1}, …, D_{s} are disjoint variable sets, each equipped with a correspondence between its variables and the points of F^{d}, then the compound LDF-assumption L_{D_{1},...,D_{s}}[r_{yes}, r_{no}, d] is defined as the intersection

L_{D_{1}}[r_{yes}, r_{no}, d] ∩ L_{D_{2}}[r_{yes}, r_{no}, d] ∩ … ∩ L_{D_{s}}[r_{yes}, r_{no}, d]

We sometimes omit the list of domains and refer to a compound LDF-assumption by L[r_{yes}, r_{no}, d].

Multiplicative Extension

In the reduction we transform Ψ_{0} from quadratic to linear (before applying the sum-check technique) using the multiplicative extension, that adds new variables instead of quadratic terms. We take the set of variables, make an LDF extension, and then add a new variable for each product of two variables.

1w.l.o.g. we assume that every degree, dimension, etc. is a natural number.

As the variables of the LDF extension are identified with the points of a geometric domain F^{d}, the variables of the multiplicative extension will be naturally identified with F^{2d} - the variable representing a product of 𝒱[x] and 𝒱[y], will be identified with the point (x, y).

Definition 7 (Multiplicative-Extension) Let h < |F|^{\frac{1}{2}} , and let 𝒱 be an arbitrary set of variables. Let v_{e} be a new variable (which will represent the value 1), and take 𝒱̂ to be the low-degree-extension of 𝒱 ∪ {v_{e}}, with parameter h. We denote, as in definition 5, H = {0, .., h} ⊂ F and

d =^{def} log_{h+1}(|𝒱| + 1), so |𝒱̂| = |F|^{d}. Every point x ∈ H^{d}

now corresponds to a variable in 𝒱 ∪ {v_{e}}, denoted 𝒱[x], and denote by e ∈ H^{d} the point such that v_{e} = 𝒱[e].

The variables in 𝒱̂ are associated with the points of F^{d}. Let us now associate them with points in F^{2d} instead, by identifying each (x, e) ∈ F^{2d} with x ∈ F^{d}. We add new variables, corresponding to the rest of the points in F^{2d}, and denote the entire variable set by 𝒱_{×}. 𝒱_{×}, together with the correspondence between its variables and the points of F^{2d}, is called the multiplicative-extension of 𝒱 with parameter h.

An assignment for a variable set 𝒱 may be extended to an LDF over the LDF extension of 𝒱. If in addition we have the multiplicative extension of 𝒱, the assignment may be naturally extended further - the assignment for each product variable 𝒱_{×}[x, y] will be assigned the product of the assignments to 𝒱[x] and 𝒱[y]. Such an extension yields an LDF over the extension variables.

Definition 8 (Proper Multiplicative-Extension) Let A : 𝒱 → F be any assignment. An assignment A_{×} : 𝒱_{×} → F is called a proper multiplicative-extension of A, if the function f defined by

∀x ∈ F^{2d} f(x) = A_{×}(𝒱_{×}[x])

is a [2hd, 2d]-LDF that obeys

1. f(e, e) = 1

2. ∀x ∈ H^{d} f(x, e) = A(𝒱[x]) , i.e. A_{×} coincides with A.

3. ∀x, y ∈ F^{d} f(x, y) = f(x, e) · f(y, e).

To enforce assignments to 𝒱_{×} to be proper multiplicativeextensions of the assignment of 𝒱, we use an LDF-assumption over 𝒱_{×}, and accompany it by a multiplicative-assumption over 𝒱_{×}.

Definition 9 (Multiplicative-Assumption) Let 𝒱_{×} be a multiplicative extension with parameter h, of a variableset 𝒱. The multiplicative-assumption χ over 𝒱_{×} is defined by χ =^{def} (A, A) where A is the set of all assignments A : 𝒱_{×} → F satisfying

∀(x, y) ∈ F^{2d} A(𝒱_{×}[(x, y)]) = A(𝒱_{×}[(x, e)])·A(𝒱_{×}[(y, e)])}

and A(𝒱_{×}[(e, e)]) = 1 1.1 Additional Definitions

In the proof of theorem 1 we define a series of equationsystems, as mentioned above. The intermediate systems in the series will be allowed to consist of conjunctions of equations ( - conjunctions for short) rather than plain equations. The degree of such a conjunction is defined as the maximum of its equations’ degrees, and its depend parameter is the total number of variables that appear in it.

An equation-system is said to be of degree d, (esp. linear or quadratic) if all of its conjunctions are of degree at most d. The depend of a system is the maximum depend of its conjunctions.

We deal with equations systems of varying parameters. Let us introduce a notation for an equation-system, that contains most of its relevant parameters.

Definition 10 Let 𝒱 be a set of variables, let A be a set of assumptions on the assignments to 𝒱, and let ϵ > 0 and d, D ≥ 1. Denote by EQ_{ϵ,D}^{d}(A|𝒱), the set of all degree-d equation-systems over variables 𝒱 with depend D, that have an (ϵ, 1)-gap under the assumptions in A. All the above parameters may be functions of n, the size of the system, which is implicit here. Throughout the proof we only use EQ_{...}^{d}(…) where d is either 1 or 2.

2 Main Theorem - the Reduction

In this section we give the reduction from gap-QS[n, F] to gap-QS[O(1), F], starting with Ψ_{0} and generating a quadratic-equation-systems that maintains the gap of Ψ_{0}, but whose equations depend only on a constant number of variables each.

Reduction Sketch. We first give a sketch of the series of reductions we intend to apply. As already mentioned, the first part of the reduction is the sum-check - the sumcheck lemma (lemma 1) reduces the depend of a given equation-system to constant, but it can only be applied to linear equation-systems. So we first transform Ψ_{0} to a linear equation-system Ψ_{1}, using the multiplicative extension, that has a new variable for each quadratic term, and introduce a multiplicative-assumption to ensure consistency. Then we apply the sum-check lemma, obtaining an equation-system Ψ_{2} with a constant depend parameter, and some additional LDF-assumptions.

Before we continue with the second part of the proof - the LDF-reader, we eliminate the multiplicative-assumption by substituting each variable back for its multiplicativeterm (Ψ_{3}). We then use the LDF-reader (lemma 2) to eliminate the LDF-assumptions (Ψ_{4}). Finally, we amplify the error probability (Ψ_{5}) and use a simple technique to transform conjunctions of equations back into equations (Ψ_{6}).

We now proceed with the details of the reduction.

Eliminating Multiplicative Terms. We construct a linear homogeneous equation-system Ψ_{1}, from the quadratic Ψ_{0}. Let 𝒱_{×} be the multiplicative-extension (see definition 7) of 𝒱 with parameter h, where h = |F|^{c′} for some 0 < c′ < \frac{1}{2} (e.g. take c′ = \frac{1}{4} ). For every ψ ∈ Ψ_{0} we shall have a linear equation in Ψ_{1}, obtained by substituting each quadratic term 𝒱[x] · 𝒱[y] in ψ with a new variable 𝒱_{×}[(x, y)]. We also multiply the constants in ψ by the variable 𝒱_{×}[(e, e)] to make it homogeneous.

Let χ be the multiplicative-assumption (see definition 9) over 𝒱_{×}. We introduce χ into Ψ_{1}, together with the LDFassumption L_{𝒱_{×}} [2hd, 2hd(log n)^{4}, 2d] where

d =^{def} log_{h+1}(|𝒱| + 1). Note that every assignment to 𝒱 can be extended to 𝒱_{×} by the proper-extension, such that both χ and the ’yes’ part of the LDF-assumption are satisfied. Therefore Ψ_{1} satisfies

Ψ_{1} ∈ EQ_{ϵ_{1},|𝒱_{×} |}^{1}(χ, L_{𝒱_{×}} [2hd, 2hd(log n)^{3}, 2d] | 𝒱_{×})

where ϵ_{1} = \frac{O(1)}{|F|} and Ψ_{0}⇒Ψ_{1}.

We use the next lemma to replace Ψ_{1} with an equationsystem of constant depend, in the price of adding new LDFassumptions. Since Ψ_{1} is linear homogeneous, it can be viewed as a set of weighted sums of variables, that are supposed to evaluate to zero. The sum-check lemma shows how to verify this by only accessing a constant number of variables.

Lemma 1 (Sum-Check) Let 0 < c_{0} < \frac{1}{2} be a constant. There exist constants c_{1}, c_{2}, c_{3} > 0, and a polynomial-time algorithm, that, given an equation-system

Ψ ∈ EQ_{ϵ,|𝒱|}^{1} (χ, L_{𝒱} [r_{yes}, r_{no}, d] | 𝒱)

where χ is an arbitrary assumption over 𝒱, r_{yes} ≤ |F|^{c_{0}} and r_{no} = r_{yes} ·(log n)^{4} and where every conjunction ψ ∈ Ψ is singleton (i.e. is actually an equation); constructs an equation-system

Ψ̃ ∈ EQ_{ϵ̃,c_{2}}^{1} (χ, L_{D_{1},..,D_{s}}[r̃_{yes}, r_{no}, c_{3}d])

where

• Ψ⇒Ψ̃

• ϵ̃ = ϵ + |F|^{−c_{1}}, and r̃_{yes} = 2d(r_{yes} + 1).

The proof of this lemma appears in the full version of the paper.

We apply the sum-check lemma to Ψ_{1} and obtain Ψ_{2}, whose depend parameter is the constant c_{2}.

Removing the multiplicative-assumption. We will now bring the multiplicative-terms back into Ψ_{2}, and discard the multiplicative-assumption χ without loosing the gap property. In every conjunction ψ ∈ Ψ_{2}, we replace every occurrence of a variable 𝒱_{×}[(x, y)] where y ≠ e, with the product 𝒱_{×}[(x, e)] · 𝒱_{×}[(y, e)]. We also add to every conjunction the equation (𝒱_{×}[(e, e)] = 1). χ may now be discarded without affecting the gap.

This yields a quadratic equation-system Ψ_{3} such that Ψ_{2}⇒Ψ_{3} and Ψ_{3} is in

EQ_{ϵ_{3},2c_{2}+1}^{2} (L_{D_{1},..,D_{s}}[2d(2hd + 1) , 2hd(log n)^{4} , O(d)])

where ϵ_{3} = ϵ_{2}.

Eliminating the LDF-assumptions. We next state the LDFreader lemma that eliminates all the LDF-assumptions, and yields an equation-system with a gap in the conventional sense.

Lemma 2 (LDF-Reader) Let c_{1}, c_{2} > 0 and 0 < c_{3}, c_{4} < 1 be arbitrary constants. Let r_{yes} < |F|^{c_{3}} and let ϵ = |F|^{−c_{4}}. There exist ω < (log n)^{3} and constants c_{5}, c_{6} > 0 such that

EQ_{ϵ,c_{1}}^{2} ({L_{D_{1},..,D_{s}}[r_{yes}, ωr_{yes}, c_{2} · log_{|F|} n]})
⇓
EQ_{ϵ̃,c_{6}}^{2} (ϕ)

where ϵ̃ < ϵ + F^{c_{5}} and ϕ denotes the empty set.

Before we can apply the LDF-Reader lemma to Ψ_{3} we need to adjust its parameters. We note that the family of equation-systems with a gap under certain LDFassumptions, is monotone decreasing in the r_{no} parameter. This means that we may decrease the r_{no} parameter in the assumptions of an equation-system, and the gap will be maintained.

The ratio between the r_{no} and r_{yes} in the assumptions of Ψ_{3} is Ω ( \frac{log^{4} n}{d} ), and thus bigger than log^{3} n. Therefore we may decrease the r_{no} parameter, and write that Ψ_{3} is in

EQ_{ϵ_{3},2c_{2}+1}^{2} (L_{D_{1},..,D_{s}}[2d(2hd + 1) , ω · 2d(2hd + 1) , O(d)])

where ω is the parameter that appears in the LDF-reader lemma. Now we can apply the lemma to Ψ_{3}, obtaining Ψ_{4}. Ψ_{4} is almost the desired gap-QS instance, except for two small differences: It is a system of conjunctions rather than equations, and its error-probability is some |F|^{−c} rather than \frac{2}{|F|}.

We amplify the error-probability by setting k = ⌈ \frac{1}{c} ⌉, and transforming Ψ_{4} = {ψ_{1}, .., ψ_{m}} into

Ψ_{5} = {(ψ_{i_{1}}) ∧ ⋯ ∧ (ψ_{i_{k}}) | 1 ≤ i_{1}, …, i_{k} ≤ m}

The error probability is raised to the power k, thus obtaining a ( \frac{1}{|F|} , 1)-gap.

Ψ_{5} is still a system of conjunctions, rather than equations. This is solved by the following (final) transformation. We replace every conjunction ψ = φ_{1} ∧ ⋯ ∧ φ_{s} ∈ Ψ_{5} with all possible (|F|^{s}) linear combinations of the equations φ_{i}:

Ψ_{ψ} =^{def} {∑_{i=1}^{s} α_{i} · φ_{i} : α_{1}, .., α_{s} ∈ F}

where a linear combination of equations is defined in the obvious way.

It is easy to see that the system of equations Ψ_{6} = ∪_{ψ∈Ψ_{5}}Ψ_{ψ} obeys Ψ_{5}⇒Ψ_{6}, since any assignment that did not satisfy a conjunction ψ, cannot satisfy more than \frac{1}{|F|} of the equations in Ψ_{ψ}. The error probability increases by no more than \frac{1}{|F|}, hence Ψ_{6} ∈ gap-QS[O(1), F].

The reduction we have described implies that deciding whether s(Ψ_{6}) = 1 or s(Ψ_{6}) ≤ \frac{2}{|F|} enables deciding whether s(Ψ_{0}) = 1 or s(Ψ_{0}) ≤ \frac{2}{|F|}; hence gap-QS[O(1), F] is NPhard.

3 Reading LDFs Consistently

In this section we prove the following lemma, showing how to eliminate LDF-assumptions, and remain with a gap in the conventional sense. This lemma can be alternatively viewed as a low-degree-test whose error-probability is exponentially small in the number of bits accessed.

Lemma 2 (LDF-Reader) Let c_{1}, c_{2} > 0 and 0 < c_{3}, c_{4} < 1 be arbitrary constants. Let r_{yes} < |F|^{c_{3}} and let ϵ = |F|^{−c_{4}}. There exist ω < (log n)^{3} and constants c_{5}, c_{6} > 0 such that

EQ_{ϵ,c_{1}}^{2} ({L_{D_{1},..,D_{s}}[r_{yes}, ωr_{yes}, c_{2} · log_{|F|} n]})
⇓
EQ_{ϵ̃,c_{6}}^{2} (ϕ)

where ϵ̃ < ϵ + F^{c_{5}} and ϕ denotes the empty set.

We prove this lemma via three sub-lemmas. Let us first state the lemmas and sketch the proof, and then proceed to the proof itself.

The main idea is to take an equation-system Ψ and repeatedly replace its assumptions, until ultimately they can be easily verified (i.e. by accessing a constant number of additional variables). Then, by adding the appropriate verification tests to the conjunctions, we eliminate the need for assumptions altogether.

We employ two main techniques for achieving such equation-system reductions. One technique reduces the dimension of the LDFs in the LDF-assumptions, and the other reduces the degree (r_{no} and r_{yes}). Then, when the LDF-assumptions are of very low degree and dimension, (namely, they are [O(log log n), O(log log n), O(1)] assumptions) we use a third linearization technique (similar to [ALM^{+}92]) that eliminates the assumptions altogether (by verifying them in the body of the conjunctions).

The first technique, named cube representation, uses geometric properties of domains, and their sub-cubes, to replace [r_{yes}, r_{no}, d]-assumptions by [r_{yes}, r_{no}, O(1)]- assumptions hence the dimension of the LDF becomes constant, while the total degree remains the same:

Lemma 3 (Cube-Representation) Fix a constant 0 < c < 1, and let r_{yes} ≤ |F|^{c}, and r_{no} = ω · r_{yes} where 1 ≤ ω < (log n)^{3}. Also assume ϵ = |F|^{−c_{2}} for some 0 < c_{2} < 1 , d ≤ log_{|F|} n and D = O(1). There exists α = |F|^{−c_{3}}, for some constant 0 < c_{3} < 1, such that

EQ_{ϵ,D}^{2}({L[r_{yes}, r_{no}, d]})
⇓

EQ_{ϵ+α,3D}^{2} ({L[r_{yes}, r_{no}, D + 3]})

Moreover, there exists a reduction algorithm between the above sets with the following property. If K bounds, for an input system Ψ, the number of different assumptiondomains that have variables in a single conjunction of Ψ, then

• The depend parameter of the output system is only D + 2K.

• The bound, K, is maintained in the output system.

The second technique, named embedding extension, replaces [r_{yes}, r_{no}, O(1)] assumptions by [r̃_{yes}, r̃_{no}, d]- assumptions where r̃_{no} and r̃_{yes} are significantly smaller than r_{yes} and r_{no}, while the dimension d is only slightly increased.

In essence r_{yes} and r_{no} are of approximately the same size. For technical reasons, the embedding extension ’works’ only if the ratio \frac{r_{no}}{r_{yes}} is large enough. Every iterative application of the embedding extension technique ’eats up’ some of this ratio. This is the reason we needed the sum-check lemma and the multiplication lemma to generate assumptions where \frac{r_{no}}{r_{yes}} = (log n)^{O(1)}.

Lemma 4 (Embedding Extension) Fix a constant t. For any k = O(log_{|F|} n), if \frac{r_{no}}{r_{yes}} ≥ kt then

EQ_{ϵ,D}^{2}({L_{D_{1},..,D_{s}}[r_{yes}, r_{no}, t]})
⇓
EQ_{ϵ,D}^{2} (\{L_{D̃_{1},..,D̃_{s}}[kt · \sqrt[k]{r_{yes}}, \frac{r_{no}}{r_{yes}} · \sqrt[k]{r_{yes}}, kt]\})

Moreover, there is a linear reduction between the above, that maintains the bound on the number of different assumptiondomains that appear in each conjunction.

This lemma holds, in fact, for any t = O(log_{|F|} n). We state it for t = O(1) since this how we use it.

The lemma can only be applied for k = O(log_{|F|} n), hence the dominating term in the new degree will usually be \sqrt[k]{r_{yes}}. Since the k parameter determines how fast the degree decreases, choosing k as large as possible gives the greatest reduction of the degree, well worth the increase in the dimension.

We alternate the use of these two techniques a constant (at most ⌊ \frac{1}{1−β} ⌋ + 2) number of iterations until we reach an equation-system with [O(log log n), O(log log n), O(1)]- assumptions. We then use a linearization technique that by transforming the LDF-assumptions into linear assumptions, and then actually assuring the linear assumptions by interpolation, eliminates the need for assumptions altogether:

Lemma 5 (Linearization) Fix c > 0 and let ϵ = |F|^{−c}. Then there exists some constant 0 < c′ < 1 such that

EQ_{ϵ,O(1)}^{2} ({L[O(log log n), O(log log n), O(1)]})
⇓
EQ_{ϵ̃,O(1)}^{2}(ϕ)

where ϵ̃ = ϵ + |F|^{c′}

Having stated the lemmas, we turn to prove the LDF-reader lemma (lemma 2). The proofs of sub-lemmas 3 and 4 follow in the next subsections. Due to space limitations, the proof of lemma 5 only appears in the full version of the paper.

Proof: (of lemma 2) We begin with an equation-system

Ψ_{0} ∈ EQ_{ϵ,O(1)}^{2} ({L[|F|^{c_{3}} , ω · |F|^{c_{3}} , O(log_{|F|} n)]}) where ω < log^{3} n is a parameter soon to be stated. We shall show a sequence of equation-reductions

Ψ_{0}⇒Ψ_{1}⇒ … ⇒Ψ_{l}

such that l = O( \frac{1}{1−β}) and

Ψ_{l} ∈ EQ_{ϵ^{O(1)},O(1)}^{2}(ϕ)

Since the reduction relation ’⇒’ is transitive (as long as it is composed a constant number of times), we get Ψ_{0}⇒Ψ_{l} and end the proof. The transition from each system to the next is done via one of the above three lemmas. We begin by applying lemmas 3 and 4 iteratively, and end with one application of lemma 5.

Choosing Parameters. For convenience we denote δ =^{def} 1− β and Δ =^{def} ⌊ \frac{1}{δ} ⌋. We apply lemma 3 to Ψ_{0}, and then

lemma 4 to the result, with parameter k =^{def} log_{|F|} n. The outcome is denoted Ψ_{1}. We will then apply this double transformation to Ψ_{1} and get Ψ_{2}, and continue iteratively until we have Ψ_{Δ}. Then we will do it twice more, now with smaller k parameters, getting Ψ_{Δ+1} and Ψ_{Δ+2}. Over all we apply the double iterations Δ + 2 times at the most.

We next compute the initial ratio ω, between the r_{yes} and r_{no} parameters of Ψ_{0}, that we need in order to legally apply the sequence of transformations. Combining the application of lemma 3 and then lemma 4 with parameter k affects the parameters of a system Ψ as follows:

EQ_{ϵ,D}^{2}({L[r_{yes}, r_{no}, d]})

by lemma 3,  ⇓

EQ_{ϵ+α,D+K}^{2}({L[r_{yes}, r_{no}, D + 3]})

by lemma 4,  ⇓
EQ_{ϵ+α,D+K}^{2} (L [k(D + 3)· \sqrt[k]{r_{yes}} , \frac{r_{no}}{r_{yes}} · \sqrt[k]{r_{yes}} , k(D + 3)])

For the first transformation to be legal we need \frac{r_{no}}{r_{yes}} ≤ log^{3} n. We also want the final r_{no} parameter to be no smaller than the r_{yes} parameter. The double lemma application decreases the ratio between r_{no} and r_{yes} by a factor of k(D+3), so for the iterative application we need the first \frac{r_{no}}{r_{yes}} ratio to be smaller than log^{3} n, and the last ratio to be at least 1.

For each Ψ_{i} in the sequence, denote

Ψ_{i} ∈ EQ_{ϵ+iα,D+2iK}^{2} (L[r_{yes}_{,i} , r_{no}_{,i} , d_{i}])

Then d_{i} = k(D_{i−1} + 3) = k(D + 2K(i − 1) + 3) ≤ (D + 2K(Δ + 2) + 3)k ≤ 10DΔk and therefore

\begin{matrix}r_{no} & ,i \\ r_{yes} & ,i \end{matrix} = \frac{r_{no}_{,i−1}}{d_{i}r_{yes}_{,i−1}} ≥ \frac{1}{10DΔk} · \begin{matrix}r_{no} & ,i−1 \\ r_{yes} & ,i−1 \end{matrix}

so each double transformation ’eats up’ at most 10DΔk of the \frac{r_{no}}{r_{yes}} ratio, where k is the parameter chosen for the embedding. The k’s we use do not exceed log_{|F|} n ≡ log^{δ} n, and we make at most Δ + 2 double transformations, so taking the initial ω to be

ω =^{def} (10DΔ log^{δ} n)^{Δ+2} = O(log^{δ(Δ+2)} n) < log^{3} n

ensures that all the transformations are legal, and that the final r_{no}/r_{yes} ratio is at least 1.

We apply the double transformation iteratively on Ψ_{0}, with parameter k = log_{|F|} n. By induction on the double transformation parameters, the size of r_{no}_{,i}, r_{yes}_{,i}, is

∀0 ≤ i < Δ r_{yes}_{,i}, r_{no}_{,i} ≤ 2^{O((log n)^{1−(i+1)δ})}

specifically, for some i ≤ Δ,

r_{yes}_{,Δ}, r_{no}_{,Δ} ≤ 2^{O(log^{δ} n)}

We stop iterating at the first i which satisfies the above. The obtained system is denoted by Ψ_{Δ} for simplicity. The degree of the LDF-assumptions in Ψ_{Δ} is significantly smaller than what we started with, but it is still not small enough. We therefore repeat the double transformation twice more, now choosing smaller k parameters (since the other parameters have shrunk, k is now dominant in determining the assumptions degree of the result of the transformation).

We choose k = log_{2}(r_{yes}_{,Δ}) for the first transformation, thus getting a system Ψ_{Δ+1}, and then take k = log_{2}(r_{yes}_{,Δ+1}) for the second transformation, which obtains Ψ_{Δ+2}. By doing the calculations, which we omit, we get that r_{yes}_{,Δ+2} ≤ r_{no}_{,Δ+2} = O(log log n), and that also d_{Δ+2} = O(log log n).

With a final application of lemma 3 we obtain an equationsystem Ψ_{Δ+2 \frac{1}{2}} with the same degrees r_{yes}_{,Δ+2 \frac{1}{2}} = r_{yes}_{,Δ+2}, and r_{no}_{,Δ+2 \frac{1}{2}} = r_{no}_{,Δ+2} but with d_{Δ+2 \frac{1}{2}} = O(1). We are now ready to apply lemma 5. We thus obtain an equationsystem Ψ_{3}, Ψ_{Δ+2 \frac{1}{2}} ⇒Ψ_{Δ+3}, where

Ψ_{Δ+3} ∈ EQ_{ϵ^{∗},O(Δ)}^{2} (ϕ)

for ϵ^{∗} = ϵ_{0} +(Δ+3)·α+ \frac{1}{|F|} = |F|^{−c^{∗}} for some 0 < c^{∗} < 1.

3.1 Cube Representation

In this subsection we show a general algorithm that, given a system with a constant depend and a gap under [r_{yes}, r_{no}, d]- LDF-assumptions, generates a system with LDF-assumptions of the same degree, but of constant dimension. The generated system will maintain the gap of the original system. The depend parameter will not be increased by much.

Lemma 3 (Cube-Representation) Fix a constant 0 < c < 1, and let r_{yes} ≤ |F|^{c}, and r_{no} = ω · r_{yes} where 1 ≤ ω < (log n)^{3}. Also assume ϵ = |F|^{−c_{2}} for some 0 < c_{2} < 1 , d ≤ log_{|F|} n and D = O(1). There exists α = |F|^{−c_{3}}, for some constant 0 < c_{3} < 1, such that

EQ_{ϵ,D}^{2}({L[r_{yes}, r_{no}, d]})
⇓

EQ_{ϵ+α,3D}^{2} ({L[r_{yes}, r_{no}, D + 3]})

Moreover, there exists a reduction algorithm between the above sets with the following property. If K bounds, for an input system Ψ, the number of different assumptiondomains that have variables in a single conjunction of Ψ, then

• The depend parameter of the output system is only D + 2K.

• The bound, K, is maintained in the output system.

We begin with an equation-system Ψ ∈ EQ_{ϵ,D}^{2}({L[r_{yes}, r_{no}, d]}). Ψ has a polynomial number of LDF-assumptions, each over a variable-set corresponding to F^{d} (these variable-sets are pairwise disjoint). We would like to substitute these d-dimensional LDF-assumptions with LDF-assumptions of constant dimension, namely (D + 3).

Suppose we substitute an assumption L over a variableset D, with many LDF-assumptions, one for each (D + 3)- dimensional affine subspace of D (Since the variables of D correspond to points of F^{d}, we regard D both as a variableset and as a geometric domain). The intersection of these new assumptions is exactly equal to L.

However, the (D + 3)-dimensional affine subspaces of D ((D+3)-cubes for short) are far from being disjoint, and we cannot have LDF-assumptions over intersecting domains (see explanation following definition 6 in subsection 1). We overcome this problem by duplicating the variables: we add a new variable-set for each (D + 3)-dimensional affine subspace of D.

Then, for each ψ ∈ Ψ, we construct a set Ψ′_{ψ} of conjunctions that simulate ψ by replacing the original variables with duplicates, and then somehow verifying consistency between the duplicates and the original variables.

The Construction of Ψ′

We will describe the construction of an equation-system Ψ′ ∈ EQ_{ϵ+α,D+2K}^{2}({L[r_{yes}, r_{no}, D + 3]}) from Ψ, such that Ψ⇒Ψ′.

Variables. Ψ′ will have the variables of Ψ, and also additional variables. Let D be an assumption-domain in Ψ. For each (D + 3)-cube C ⊂ D, we add a new set C[·] of cubevariables, with a distinct duplicate C[x] for each variable D[x] ∈ C. Note that now each point in D has many variables representing it, one for each (D + 3)-cube containing it.

Assumptions. Let D be an assumption-domain in Ψ. For each cube C ⊂ D, Ψ′ will have an [r_{yes}, r_{no}, D + 3]- assumption on C[ ·]. These assumptions replace the [r_{yes}, r_{no}, d]-assumption on D. The assumption replacement can be summarized by

L_{D}[r_{yes}, r_{no}, d]
↓
{L_{C[ ·]}[r_{yes}, r_{no}, D + 3] : C is a (D + 3)-cube in D}

The Conjunctions. For every ψ ∈ Ψ we shall have a set of conjunctions Ψ′_{ψ}, and set

Ψ′ =^{def} ⋃_{ψ∈Ψ} Ψ′_{ψ}

The conjunctions in Ψ′_{ψ} will simulate ψ, only they will refer not to the original variables, but to cube-variable duplicates. In addition, the conjunctions in Ψ′_{ψ} will have consistency equations verifying the consistency of the cubevariables with the original variables.

Take a conjunction ψ ∈ Ψ. It depends on variables from K assumption-domains^{2}, D_{1}, …, D_{K}, called the assumption domains of ψ. ψ has at most D variables from each D_{i}, since the total depend is D. For each i, take x_{i} ⊆ D_{i} to be an arbitrary D-cube that contains the variables of ψ in D_{i} - x_{i} is called the base of ψ in D_{i}.

Definition 11 Let D = F^{d} and let x ⊆ D be a subset. We denote by S_{x} the set of (D + 3)-cubes in D that contain x.

The set Ψ′_{ψ} is defined as follows. For every choice of points

y_{i} ∈ D_{i} and cubes C_{i} ∈ S_{x_{i}∪{y_{i}}}, i = 1, .., K, Ψ′_{ψ} has a

conjunction ψ[y_{1}, …, y_{K}, C_{1}, …, C_{K}] ∈ Ψ′_{ψ} that consists of:

• The conjunction ψ, where every variable of the form D_{i}[x] is substituted by C_{i}[x] (C_{i} contains base of ψ in D_{i}, therefore it contains the necessary variables).

• The equations (C_{i}[y_{i}] = D_{i}[y_{i}]), for 1 ≤ i ≤ K. These are called the consistency test equations.

The variables of ψ[y_{1}, …, y_{K}, C_{1}, …, C_{K}] ∈ Ψ′, unlike those of ψ in Ψ, are not guaranteed to have values of global LDFs on the D_{i}’s. However, we will show that the gap is maintained in Ψ′, because in almost all the conjunctions of Ψ′_{ψ}, if the consistency tests succeed, the variables have values of permissible LDFs on the D_{i}’s. We will elaborate on this when we prove that Ψ′ maintains the gap.

Remarks About the Construction. Ψ′ may contain new variable domains and LDF-assumptions, that no conjunction really has variables from. These domains may as well be discarded. We also note that every set Ψ′_{ψ} has the same number of conjunctions - this fact is used later.

The Parameters of Ψ′

The assumptions of Ψ′ are [r_{yes}, r_{no}, D + 3]-LDF assumptions. The depend of each conjunction equals the depend of ψ, plus the depend of the K consistency test equations. The depend is thus bounded above by D + 2K.

We therefore have Ψ′ ∈ EQ_{1,D+2K}^{2}({L[r_{yes}, r_{no}, D + 3]}). i.e. Ψ′ has the properties claimed in the lemma, except for the gap property, which remains to be verified.

The Gap

Due to space limitations we only give a general description of the proof of the gap property.

2ψ may depend on variables from less than K assumptiondomains, in which case we associate it with arbitrary domains.

In the yes case, where Ψ is completely satisfiable, it is easy to take a satisfying assignment for Ψ and extend it to a satisfying assignment of Ψ′. Ψ′ has the variables of Ψ, which remain with the same assignment, and also new variables. In the construction, each new variable was associated with an old one, so it is natural to assign it with the value of the variable it represents. It is easy to verify that this extension of the assignment indeed yields a satisfying (legal) assignment for Ψ′.

In the no case, we show that each assignment of Ψ′ can be (randomly) translated to an assignment of Ψ that satisfies almost the same fraction. In the proof we use the low-degree-test lemma of [RS97], to show that the LDFassumptions on the cubes in Ψ′, force the assignments to the domains to consist of so called permissible LDFs. The assignment of Ψ′ is translated to an assignment for Ψ by assigning each domain with one of its permissible LDFs.

3.2 The Embedding Extension

In this section we state and prove lemma 4, showing how to replace [r_{yes}, r_{no}, t]-assumptions with considerably lowerdegree assumptions, slightly increasing the dimension.

First we state a proposition that shows how an LDF over a constant dimensional domain F^{t} can be embedded as a much lower-degree LDF over a domain of larger dimension F^{tk}. An LDF over F^{t}, when embedded over F^{tk}, yields an LDF of degree roughly the k’th root of the original degree.

The idea behind the representation is simple. If a variable x in a polynomial, is replaced by several variables which correspond to powers of x (say y_{1} = x, y_{2} = x^{3}, y_{3} = x^{27}), then a polynomial of high degree in x such as x^{28}+x^{10} can be represented by polynomial over more variables, but also of considerably lower degree (y_{1})(y_{3}) + (y_{1})(y_{2})^{2}.

Proposition 6 Let t be a constant and let k be some parameter. There exists an injective map M : F^{t} → F^{tk} with the following properties:

• For any [r, t]-LDF f : F^{t} → F, there is a [btk, tk]- LDF f_{e} on F^{tk} such that

∀x ∈ F^{t} : f(x) = f_{e}(M(x))

where b =^{def} \sqrt[k]{r}.

• M is a polynomial manifold of degree b^{k−1} = r_{yes}/b in F^{tk}. (Hence for any [r̃, tk]-LDF f_{e} on F^{tk}, its restriction to M, f_{e} ∘ M : F^{t} → F is an [r̃ · b^{k−1}, t]-LDF over F^{t}.)

Proof: The embedding map M is defined as follows. For x̄ = (x_{1}, …, x_{t}) ∈ F^{t}, M(x̄) is the point ȳ = (y_{1}, …, y_{t}) ∈ F^{tk}, where for each i

y_{i} = (y_{i,0}, .., y_{i,k−1}) =^{def} ((x_{i}), (x_{i})^{b}, (x_{i})^{b^{2}}, …, (x_{i})^{b^{k−1}})

It is clear that M is an injective map and a manifold of degree b^{k−1}. This gives the second statement in the proposition. As for the first statement, consider an [r, t]-LDF f over F^{t}. We construct the corresponding LDF f_{e} over F^{t·k} by replacing the monomials of f, x_{i}^{j}, with (y_{i,0})^{b_{0}}(y_{i,1})^{b_{1}}...(y_{i,k−1})^{b_{k−1}} where b_{0}b_{1}...b_{k−1} is the base b representation of j, i.e. j = ∑_{p=0}^{k−1} b_{p} · b^{p}.

It is easy to see that ∀x, f(x) = f_{e}(M(x)) and evaluating f on any point x ∈ F^{t} can be done in polynomial time by evaluating f_{e} on M(x) ∈ F^{tk}. One may think of the embedding as adding redundancy in the representation of a point, in order to make the computation of the LDF ’easier’.

The dimension of f_{e} is the dimension of f times k, yet the degree in each variable is < b, hence the total degree is b · tk. This completes the proof of the proposition.

Lemma 4 (Embedding Extension) Fix a constant t. For any k = O(log_{|F|} n), if \frac{r_{no}}{r_{yes}} ≥ kt then

EQ_{ϵ,D}^{2}({L_{D_{1},..,D_{s}}[r_{yes}, r_{no}, t]})
⇓
EQ_{ϵ,D}^{2} (\{L_{D̃_{1},..,D̃_{s}}[kt · \sqrt[k]{r_{yes}}, \frac{r_{no}}{r_{yes}} · \sqrt[k]{r_{yes}}, kt]\})

Moreover, there is a linear reduction between the above, that maintains the bound on the number of different assumptiondomains that appear in each conjunction.

Proof: Let Ψ ∈ EQ_{ϵ,D}^{2}({L_{D_{1},..,D_{s}}[r_{yes}, r_{no}, t]}). We will show a general algorithm to construct Ψ̃, such that Ψ̃ ∈ EQ_{ϵ,D}^{2} (\{L_{D̃_{1},..,D̃_{s}}[kt · \sqrt[k]{r_{yes}}, \frac{r_{no}}{r_{yes}} · \sqrt[k]{r_{yes}}, kt]\}). Recall that the D_{i}’s are pairwise disjoint, and each D_{i} is identified with a copy of F^{t} by the correspondence x → D_{i}[x]. For each i, we add a set of new variables D̃_{i} that ’extends’ D_{i} – D̃_{i} is identified with an extended domain F^{tk}. This accounts for the restriction k = O(log_{|F|} n), since we want the size of Ψ̃ to be polynomial in the size of Ψ.

Constructing Ψ̃. We substitute the assumption L_{D_{i}}[r_{yes}, r_{no}, t] for LD̃_{i}[r̃_{yes}, r̃_{no}, kt], where

r̃_{no} = \frac{r_{no}}{r_{yes}} · b
r̃_{yes} = kt · b

and b = \sqrt[k]{r_{yes}}. Every occurrence of the variable D_{i}[x] in a conjunction is replaced by the new variable D̃_{i}[M(x)] where M is the map from proposition 6, hence depend(Ψ̃) = depend(Ψ).

The variables D_{i} no longer appear in any of the conjunctions and are discarded. Note that the variables from D̃_{i} that appear in the conjunctions are only those on the manifold M(D_{i}) ⊂ D̃_{i}. The rest of the variables seem to have been artificially added, for the sake of the assumption. In fact, there will be many conjunctions that depend on these variables when we eliminate the LDF-assumptions (e.g. when the cube representation lemma is applied, and the new domains are broken into cubes).

Maintaining the Gap. Proving that Ψ̃ maintains the gap of Ψ is both relatively easy. We only only give a description of it, due to space limitations.

In the yes case, we just use proposition 6 to extend a satisfying for Ψ, and get a satisfying assumption for Ψ̃. In the no case, we use the fact that the embedding is a polynomial manifold, to translate an assignment for Ψ̃ to an assignment for Ψ that satisfied the exact fraction of equations. This is done by restricting the assignments of the D̃_{i}’s, to the embedded D_{i}’s.

4 Discussion

We would like to suggest the following conjecture, which can be viewed as the gap-QS parallel for the [BGLR93] conjecture:

Conjecture 3 ∃c > 0 constant, such that gap-QS[O(1), F] is NP-hard for |F| = Θ(n^{c}).

As the BGLR conjecture states that proofs are verifiable with a polynomially small error by accessing a constant number of logarithmic sized variables, we claim that it is achievable even by tests formed as quadratic-equations.

References

[ABMP98] M. Alekhnovich, S. Buss, S. Moran, and T. Pitassi. Minimum propositional proof length is NP-hard to linearly approximate. Manuscript, 1998.

[ALM^{+}92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 13–22, 1992.

[AS92] S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 2–13, 1992.

[AS97] Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 485–495, El Paso, Texas, 4–6 May 1997.

[BFL91] L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991.

[BGLR93] M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient multi-prover interactive proofs with applications to approximation problems. In Proc. 25th ACM Symp. on Theory of Computing, pages 113–131, 1993.

[DS98] I. Dinur and S. Safra. Monotone-minimum-satisfying assignment is NP-hard for almost polynomial factors. Manuscript, 1998.

[HPS93] J. Hastad, R. Phillips, and S. Safra. A wellcharacterized approximation problem. Information Processing Letters, 47:301–305, 1993.

[LY94] Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960–981, 1994.

[Raz98] Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, June 1998.

[RS97] R. Raz and S. Safra. A sub-constant errorprobability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, pages 475–484, 1997.