Authors Subhash Khot, Muli Safra,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887
www.theoryofcomputing.org
S PECIAL ISSUE : A NALYSIS OF B OOLEAN F UNCTIONS
A Two-Prover One-Round Game
with Strong Soundness
Subhash Khot∗ Muli Safra
Received July 2, 2012; Revised May 7, 2013; Published December 6, 2013
Abstract: We show that for any fixed prime q ≥ 5 and constant ζ > 0, it is NP-hard to
distinguish whether a two-prover one-round game with q6 possible answers has value at least
1 − ζ or at most 4/q. The result is obtained by combining two techniques: (i) An Inner PCP
based on the point versus subspace test for linear functions. The test is analyzed Fourier
analytically. (ii) The Outer/Inner PCP composition that relies on a certain sub-code covering
property for Hadamard codes. This is a new and essentially black-box method to translate a
codeword test for Hadamard codes to a consistency test, leading to a full PCP construction.
As an application, we show that unless NP has quasi-polynomial time deterministic algo-
rithms, the Quadratic Programming Problem is inapproximable within factor (log n)1/6−o(1) .
ACM Classification: F.1.3
AMS Classification: 68Q17
Key words and phrases: approximation, approximation algorithms, Fourier transform, inapproximabil-
ity, label cover, Grothendieck inequality, linearity testing, PCP, probabilistically checkable proofs
1 Introduction
It is well known that for many NP-hard problems, even computing approximate solutions is computa-
tionally hard. In particular, it is known that given a satisfiable instance of 3SAT, it is NP-hard to find an
A preliminary version of this paper appeared in the Proceedings of the 52nd IEEE FOCS, 2011 [22].
∗ Research supported by NSF CAREER grant CCF-0833228, NSF Expeditions grant CCF-0832795, NSF Waterman Award
and BSF grant 2008059.
© 2013 Subhash Khot and Muli Safra
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a028
S UBHASH K HOT AND M ULI S AFRA
assignment that satisfies a β fraction of the constraints for some absolute constant β < 1. Indeed, this is
precisely the statement of the PCP Theorem [14, 4, 3], which serves as the starting point for many such
inapproximability results for various NP-hard problems, e. g., [1, 6, 16, 17, 13].
The PCP Theorem may equivalently be stated from a proof checking viewpoint (and this viewpoint
played a decisive role in its discovery). From the proof checking viewpoint, the PCP Theorem states
that NP has probabilistically checkable proofs with a very efficient verifier. Specifically, there is a way
to write a proof for an NP-statement such that its correctness can be verified by a probabilistic verifier
that uses logarithmic randomness and a constant number of queries to the proof. The proof system is
complete in the sense that a correct proof of a correct statement is accepted with probability 1 and is also
sound in the sense that any proof of an incorrect statement is accepted with probability strictly bounded
away from 1 (this probability can be reduced to an arbitrarily small constant by running the verifier O(1)
times). The equivalence between the proof checking viewpoint and the inapproximability viewpoint
(i. e., the statement of the PCP Theorem as inapproximability of 3SAT as quoted in the beginning),
going back to [11, 14], though not difficult to prove, has led to many illuminating insights and strong
inapproximability results over the last two decades. By now, it is a standard practice in PCP literature to
freely switch between the proof checking viewpoint and the inapproximability viewpoint and we follow
the practice in this paper.
A vast majority of the inapproximability results start by reducing the hard 3SAT instance given by
the PCP Theorem to a problem called Label Cover, introduced in [1], which is equivalently viewed as a
2-Prover-1-Round Game. A 2P1R Game (see Definition 2.1) has a parameter R that denotes the number
of different answers each prover may give on a fixed question. In this paper, all games considered are
projection games where the answer of the first prover uniquely determines the answer of the second
prover (if the verifier is to accept). For a projection game, the number of answers for the two provers
may be different and R denotes the larger of the two numbers. The PCP Theorem combined with Raz’s
Parallel Repetition Theorem [29] gives the following result.
Theorem 1.1. There exists an absolute constant γ > 0 such that for all large constant R, it is NP-hard to
distinguish whether the value of a (projection) 2P1R Game with R answers is 1 (called the completeness
parameter) or at most 1/Rγ (called the soundness parameter).
In this paper, we investigate the trade-off between the number of answers R and the soundness
parameter. Given the central nature of 2P1R Games, we believe this is a natural pursuit. It is easy
to see that the soundness must be at least Ω(1/R), since the provers may give a random answer and
succeed with probability Ω(1/R). The exponent γ in the above theorem is unspecified in Raz’s paper
(and the subsequent works of Holenstein [18] and Rao [28]) and even if one were to compute it, it would
presumably be very tiny.1 The main result in this paper is that the above theorem holds essentially with
γ = 1/6, albeit with imperfect completeness.
Theorem 1.2 (Main Theorem). For any fixed prime q ≥ 5 and constant ζ > 0, it is NP-hard to distinguish
whether a 2P1R Game with R = q6 answers has value at least 1 − ζ or at most 4/q.
1 If the value of a game is 1 − α, then the value of the k-wise repeated game is at most (1 − α p )ck for some absolute constants
c and p. We have improvements p = 32, 3 and for projection games p = 2 from [29, 18, 28] respectively. However, c still
remains unspecified and hence the exponent γ remains unspecified in Theorem 1.1.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 864
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
The exponent γ does play a role in some inapproximability results. For instance, Arora et al. [2] show
that the Quadratic Programming Problem is inapproximable within factor (log n)γ . This is the problem of
maximizing a quadratic form ∑ni, j=1 ai j xi x j where aii = 0 for 1 ≤ i ≤ n and the variables xi are restricted
to be {−1, 1}-valued. The problem is known to be approximable within factor O(log n) [23, 26, 10].
We obtain the following improved inapproximability result. In fact this application was our original
motivation.
O(1/ε)
Theorem 1.3. For an arbitrarily small constant ε > 0, unless NP ⊆ DTIME(2(log n) ), no polynomial
time algorithm can approximate the Quadratic Programming Problem within factor (log n)1/6−ε .
This result requires the analogue of Theorem 1.2 when R is a large enough growing function of
the instance size. We make this statement precise below. Though the statement is a bit cumbersome, it
might be useful for future reference. We note that Theorem 1.2 has been recently improved by Chan [9],
essentially achieving γ = 1/2. His result is described in more detail in Section 1.2. His reduction however
leads to a large blow-up in the instance size and does not apply for large enough values of R and does not
lead to improvement to Theorem 1.3.
Theorem 1.4. For any integer q that is a power of 2, there is a reduction from a SAT instance of size n to
a 2P1R Game with R = q6 answers such that:
2 24 6 2
• The size of the 2P1R Game is 2O((log n+log q) log n·q log q) .
q6 log2 q
• If the SAT instance is satisfiable, the value of the 2P1R Game is at least 1 − .
nΩ(1)
• If the SAT instance is unsatisfiable, the value of the 2P1R Game is at most 4/q.
One technical contribution of the paper, perhaps more interesting for future research, is an essentially
black-box method to translate a codeword test for Hadamard code (i. e., a linearity test) to a consistency
test, leading to a full PCP construction. We state this as informal Theorem 1.5 towards the end of this
section.
1.1 Overview of proofs and techniques
We prove Theorem 1.2 by constructing a PCP (for an NP-complete language) that makes two queries
to a proof: one query reads a symbol over an alphabet of size q and the other reads a symbol over an
alphabet of size q6 . The PCP has completeness 1 − ζ and soundness at most 4/q. As is standard in the
PCP literature, the PCP is obtained by composing the so-called Outer PCP and Inner PCP.
Inner PCP The Inner PCP is essentially a probabilistic testing procedure that tests whether a given
function f : Fm
q → Fq satisfies a desired property. Three types of tests have generally been used depending
on the desired setting of parameters, e. g., the number of queries, type of the acceptance predicate,
completeness and soundness, size of the proof, etc.
• The low degree test [14, 4, 5, 30] that tests whether f is a polynomial of low degree.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 865
S UBHASH K HOT AND M ULI S AFRA
• The linearity test that tests whether f is linear (= Hadamard codeword) [3, 19].
• The dictatorship test that tests whether f is a dictatorship, i. e., a function of the form f (x) = xi for
some coordinate 1 ≤ i ≤ m, e. g., [6, 16, 17].
If f satisfies the desired property (i. e., being linear, low degree, or dictatorship), then the test passes
with probability (close to) 1 and conversely, if the test passes with reasonable probability, f must have a
non-trivial agreement with another function g that has the desired property. The low degree test has been
analyzed algebraically [14, 4, 5] and also combinatorially [30] whereas the linearity and dictatorship tests
are often amenable to Fourier analysis, e. g., [19, 16, 17, 20].
In this paper, we desire an explicit and good trade-off between the alphabet size of the PCP and
the soundness parameter. At the Inner PCP level, this is achieved by a linearity test that combines the
elements of the linearity test and the low degree test. Specifically, given a function f : Fmq → Fq , we wish
to test that f is linear. The standard BLR test [8] checks whether f (x + y) = f (x) + f (y) for randomly
chosen inputs x and y. We however wish to have a 2-query test and hence we instead do a point versus
subspace test. We are given the table of values of the function f and in addition, for every subspace
W ⊆ Fm q of dimension 6, a linear function T(W ) : W → Fq that is supposed to be the restriction of f on
W (denoted f |W ). The test selects a random 6-dimensional subspace W and a random point w ∈ W and
accepts if and only if f (w) = T(W )(w). Note that the query f (w) is over an alphabet of size q and the
query T(W ) is over an alphabet of size q6 .
We achieve the following soundness guarantee: if f passes the point versus subspace test with
probability 3/q, then for some j ∈ Fq , j 6= 0, the function j · f has a Fourier coefficient with magnitude at
least 1/q2 (see Lemma 4.4). Interestingly, the test is analyzed by looking at the probability that f (and
its restriction f |W ) passes the Gowers Test f (x) − f (y) − f (z) + f (−x + y + z) = 0 for randomly chosen
x, y, z (see Section 4.1 for the reason the test is named so). The Gowers Test is considered for the purposes
of the analysis only and is not a part of the actual test. The probability of passing the Gowers Test is
related to the existence of a large Fourier coefficient (see Lemma 4.3) for function j · f for some j 6= 0.
The analysis proceeds as follows: assume that f passes the point versus subspace test with probability
1/q + δ where δ ≥ 2/q. For the sake of simplicity, assume that for every subspace W , the test passes
with probability 1/q + δ after selecting W . Thus f |W has agreement 1/q + δ with a linear function T(W ).
We show that this implies j · f |W has a large Fourier coefficient for some j 6= 0 and hence f |W passes the
Gowers Test with probability 1/q + δ 4 . We observe that the probability that f passes the Gowers Test is
the average (over W ) of the probability that f |W passes the Gowers Test, up to an additive difference of
e = 3/q4 . This implies that f passes the Gowers Test with probability 1/q + δ 4 − e ≥ 1/q + 2/q4 . From
this we conclude that for some j 6= 0, j · f has a large Fourier coefficient, with magnitude at least 1/q2 .
Thus the Gowers Test serves as a vehicle to pass from the local linearity of f to its global linearity.
This is also reminiscent of the bootstrapping method that allows the analysis of the low degree test in two
(or three) dimensions to carry over to a higher number of dimensions.
Remark It is not clear that we necessarily need a point versus `-dimensional subspace test with ` = 6
to achieve a soundness of O(1/q). Here is the limitation of our current analysis. In the Gowers Test on
f |W , dim(W ) = `, the inputs x, y, z are linearly dependent with probability Θ(1/q`−2 ). On the other hand,
when the Gowers Test is applied to the function f , the inputs x, y, z are linearly dependent with probability
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 866
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
Θ(1/qm−2 ) which is negligible. Hence we are able to claim that the probability that f passes the Gowers
Test is the average (over W ) of the probability that f |W passes the Gowers Test, but only up to an additive
difference of e = Θ(1/q`−2 ). As the above calculation shows, we desire that δ = O(1/q) and that δ 4
dominates e = Θ(1/q`−2 ), which forces us to have ` ≥ 6.
Outer PCP, Composed PCP and Sub-Code Covering Property The linearity testing primitive at the
Inner PCP level dictates that we use an Outer PCP based on a NP-hard problem with linear constraints. A
natural choice is the 3LIN problem over Fq : we are given an instance (X, Φ) where X is a set of variables
taking values in Fq and Φ is a set of linear equations, each equation depending on three variables from X.
The goal is to find an assignment σ : X → Φ that satisfies a good fraction of the equations. A well-known
result of Håstad [17] shows that for any constant η > 0, it is NP-hard to distinguish whether an instance
(X, Φ) has an assignment that satisfies 1 − η fraction of the equations (YES Case) or any assignment
satisfies at most 1/q + η fraction of the equations (NO Case).
Starting with the hard instance of 3LIN as above, one builds a 2P1R Game as follows: the first prover
is sent a set of k equations at random from Φ. Let V denote the set of 3k variables sent to the first prover.
The second prover is sent a set U ⊆ V that includes independently for 1 ≤ i ≤ k, all three variables in
the ith equation with probability 1 − β and exactly one of the three variables in the ith equation with
probability β /3 each (β will be tiny as explained later). The provers answer with assignments to V and
U respectively and the verifier accepts if and only if the assignments are consistent on U and moreover
all equations on V are satisfied. In the YES Case, the provers have a strategy to make the verifier accept
with probability at least 1 − kη whereas in the NO Case, any prover strategy makes the verifier accept
with probability at most 2−Ω(β k) (see Section 3 for a proof).
The 2P1R Game described is precisely the so-called Outer PCP. The composition of the Outer and
Inner PCP amounts to constructing a verifier that behaves as follows: the PCP verifier expects, for each
question V (U resp.) to the first (second resp.) prover, a Hadamard encoding of assignment to V (U
resp.). The Hadamard code is same as the table of values of a linear function fV : FVq → Fq (gU : FUq → Fq
resp.) defined by an assignment to V (U resp.). Moreover, for every V , a table of linear functions on
all 6-dimensional subspaces of FVq is expected; these linear functions are supposed to be the restrictions
of the global linear function on FVq . The verifier now picks a random question V to the first prover and
performs the point versus subspace test on the table fV and the corresponding subspaces table.
Note that it appears as if the Hadamard codes on U do not play any role (which would not make
sense). We observe that the Hadamard code on U is actually contained in the Hadamard code on V (as a
sub-code). This is because FUq ⊆ FVq where we append a vector in FUq with zeroes at positions in V \U
and think of it as a vector in FVq . Thus there is no need to have a separate Hadamard code on U (though it
helps in the analysis to think of these as virtual tables). Moreover if U ⊆ V ∩V 0 for distinct questions V
and V 0 to the first prover, we can identify the positions in Hadamard codes of V and V 0 that correspond to
the same position in the (virtual) Hadamard code of U.2
Now we look carefully at the soundness analysis of the composed PCP. Assume on the contrary
that the verifier accepts with probability 4/q and for simplicity that for every V , the verifier accepts
2 The reader might be concerned here that the 3LIN instance has imperfect completeness and whether such identification
can be done. This is a subtle and valid point: a short answer is that the identification can be done, but as mentioned in the next
paragraph, the standard trick of folding over equations is no longer allowed and the folding needs to be implemented explicitly.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 867
S UBHASH K HOT AND M ULI S AFRA
the point versus subspace test on the supposed Hadamard code f : FVq → Fq with probability 4/q. The
analysis of the Inner PCP guarantees that for some j 6= 0, j · f has a large Fourier coefficient. Thus
the function f may be list decoded by making a list of all large Fourier coefficients. Since the sum of
squared magnitudes of all Fourier coefficients is 1, the list size is bounded. Our test also incorporates
side-conditions (see Section 4.3) and ensures that the Fourier coefficients obtained as list decoding satisfy
all the equations on V (this is done in a more explicit manner than the standard folding over equations
trick which is inapplicable in our setting).
Finally we want to infer consistency between f (i. e., supposed Hadamard code on V ) and the (virtual)
supposed Hadamard codes gU : FUq → Fq on U ⊆ V . But as observed gU = f |FUq . We would like to
conclude that since j · f has a large Fourier coefficient, so do many of the j · g|U functions. This turns out
to be possible if the sub-code spaces FUq over all choices of U (weighted according to the distribution
on U for a fixed V ) cover the global space FVq almost uniformly. We term this as the sub-code covering
property. When β is sufficiently small and k is sufficiently large, we note that
2
|U| ≈ 1 − β |V | ;
3
thus the size of a typical sub-code space is q−O(β k) = 2−O(β log q·k) relative to the size of the code, there
are roughly
k
· 3β k = 2Ω(β log(1/β )·k)
βk
choices of U, and it is not unreasonable to expect that the covering property holds provided log(1/β )
log q. We formally prove this as Lemma 3.1.
Once we are able to infer the consistency of tables f = fV and gU , as usual, the list decoding and
then picking a random Fourier coefficient in the list yields a provers’ strategy in the 2P1R Game. This
yields a contradiction provided the soundness 2−Ω(β k) of the 2P1R Game is low enough, which follows if
β k is large enough.
The Codeword Test and the Consistency Test In the PCP literature, the low degree test, linearity test
and the dictatorship test at the Inner PCP level are often referred to as the codeword test and then the
Inner/Outer PCP composition amounts to extending the test to the consistency test between two (or more
as is necessary in some PCPs) supposed codewords, e. g., fV and gU as above. Often this composition
presents serious technical challenges and one needs to carefully analyze each PCP construction by itself.
Our paper shows how to translate the codeword test for Hadamard code (i. e., the linearity test), essentially
in a black-box manner, to a consistency test. In fact the tables gU are virtual and there is no separate
consistency test. As described above, the codeword test for functions fV automatically serves as a
consistency test between fV and gU , since the entries in tables fV and fV 0 that correspond to the virtual
table gU with U ⊆ V ∩V 0 are identified together. We state this observation as an informal theorem.3
Theorem 1.5 (Informal). Suppose there is a linearity test for functions f : Fm q → Fq with perfect com-
pleteness such that every function whose all Fourier coefficients are o(1) in magnitude is accepted with
3 We remark that a similar informal theorem also holds for the dictatorship test modulo the Unique Games Conjecture, with
the notion of Fourier coefficients replaced by influences of co-ordinates.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 868
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
probability at most s. Then the test can be translated to a PCP with the same predicate, almost perfect
completeness and soundness at most s + o(1).
Our informal theorem applies in particular to the results of Samorodnitsky and Trevisan[31] and
k
Engebretsen and Holmerin [12]. The first paper gives a linearity test over Fm 2 with k + 2 queries
k
and soundness 2−(2) which is translated into a PCP in the latter paper, albeit thinking of the test as a
dictatorship test with addition of noise (the former paper is able to construct a PCP with slightly worse
parameters). Our informal theorem leads to a PCP directly.
1.2 Related work
Our point versus subspace test is similar to the point versus affine line test [4, 5] and the point versus
affine plane test [30]. These tests check whether a function has degree d where d is small but still
super-constant. We are instead interested in the simplest case, i. e., d = 1. The tests in [5, 30] have the
following soundness guarantee: if a function f : Fq → Fq passes with probability δ and q > Ω((dm δ )c ),
m
0
then f must have agreement at least δ c with some degree d polynomial for some positive integers c and
c0 . We could apply their analysis to the special case d = 1. However we are interested in the explicit
values of c and c0 which are not specified in these papers and moreover we cannot afford the dependence
on m. In principle, the values of c and c0 may be computed by a rigorous examination of analysis therein
and perhaps the dependence on m is not necessary. We however skip this arduous task and instead present
a self-contained Fourier analysis of the test.
With a more careful (or different, perhaps algebraic or combinatorial along the lines of [5, 30])
analysis, it might be enough to have the point versus 2-dimensional subspace (or the point versus affine
line) test instead of the point versus 6-dimensional subspace test. If so, this would give a PCP with q2
answers and soundness O(1/q). We do not consider this as the current focus of our paper and hence do
not attempt it. Our focus is to demonstrate that it is possible to get an explicit and good trade-off between
the answer size and the soundness parameter and present the Outer/Inner PCP composition based on the
sub-code covering property. Constructing a PCP with qt answers with 1 < t < 2 and soundness O(1/q)
however seems much more challenging, if possible at all, and might require an entirely new approach.
We note that Moshkovitz and Raz [25] do provide an analysis of the point versus 2-dimensional subspace
test (Theorem 19 therein), in a rather similar way as ours, albeit using the BLR Test as an intermediate
vehicle instead of the Gowers Test. The soundness they achieve is O(1/q1/6 ), which would give exponent
γ = 1/12 in the trade-off between the alphabet size and the soundness of the test. √
A recent result of Chan [9] improves Theorem 1.2 and obtains soundness of O(log(R)/ R) for a
2P1R Game with R answers and almost-perfect completeness. (He does not get improved result for
the Quadratic Programming Problem however, due to a blow-up in the instance size.) His techniques
are entirely different and his result is more general. We do sketch his result since interestingly there
is a (loose) connection to the point versus affine line test. His general result is that for any abelian
group G and a pairwise independent subgroup H ⊆ Gk , the constraint satisfaction problem CSP(H) is
approximation resistant in a very strong sense. This is a k-CSP where the variables take values over G,
the set of satisfying assignments is H and variable translations are allowed (this is analogue of variable
negation in the boolean case). He shows that it is NP-hard to distinguish whether the instance is nearly
satisfiable or whether for any global assignment to the instance, the local assignment to a constraint, over
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 869
S UBHASH K HOT AND M ULI S AFRA
a randomly chosen constraint, is nearly uniform in Gk (after accounting for the variable translations).
Towards obtaining a result for 2P1R Games, he sets G = Fq and H ⊆ Fqq to be the set of (value tables of)
linear functions f : Fq → Fq (i. e., functions of the form f (x) = ax + b and hence |H| = q2 ). The CSP
is then viewed as a variable versus constraint 2P1R Game which resembles the point versus affine line
test for a linear function. The strong soundness guarantee of the CSP implies the soundness of the 2P1R
Game. Roughly speaking, for any assignment to the CSP variables (i. e., the first prover’s answers), the
second prover cannot do significantly better than picking a random answer (i. e., a random assignment
from H). The second prover has q2 possible answers and for a random answer, his expected agreement
with the first prover is 1/q. The soundness of the 2P1R Game is O(log q/q): one loses a logarithmic
factor since the second prover, instead of picking a random answer, can do slightly better by picking the
best possible answer, i. e., answer from H that has the best agreement with the first prover’s answers.
Finally, we remark that the focus of our results is incomparable to that of the Sliding Scale Conjecture
of Bellare et al. [7] and the Projection Games Conjecture of Moshkovitz [24]. We focus on the trade-off
between the soundness and the answer-size R of a 2P1R Game while thinking of R as a constant (or
slowly growing with the instance size) whereas these conjectures focus on the case where the (inverse of)
soundness and R are polynomial in the instance size.
2 Preliminaries
In this section, we briefly describe preliminary background and the tools used in this paper.
2.1 2-Prover 1-Round Games
Definition 2.1. A 2P1R Game G(V, U, µ, R, S, {πVU }) consists of sets of questions V, U and sets of
answers R, S for the two provers respectively, a distribution µ on the set of question pairs V × U and for
every question pair (V,U) in the support of µ, a predicate πVU : R × S → {0, 1} that defines the pairs of
accepting answers. A strategy of the provers is a map φ : V → R, φ : U → S. The value of the strategy φ
is:
val(φ , G) := Pr [πVU (φ (V ), φ (U)) = 1] .
(V,U)∼µ
The value of the game val(G) is the maximum value of any prover strategy. A Projection Game is one
where for every answer of the first prover, there is exactly one accepting answer of the second prover. For
a Projection Game, the predicate πVU can be thought of as a map πVU : R → S and the accepting answers
are of the form (r, πVU (r)) for r ∈ R. For a Projection Game, |S| ≤ |R|.
A 2P1R Game is best viewed as a game between the two provers and a verifier. The verifier picks a
random question pair (V,U) from the distribution µ, asks one question each to the two provers respectively,
and accepts if and only if the provers’ answers satisfy the predicate πVU . The probability of acceptance
by the verifier is same as the value of the provers’ strategy.
Definition 2.2. Given a 2P1R Game G(V, U, µ, R, S, {πVU }), the k-wise repeated game is
G⊗k (Vk , Uk , µ k , Rk , Sk , {πVk 0U 0 }) ,
where for V 0 = (V1 , . . . ,Vk ) and U 0 = (U1 , . . . ,Uk ), πVk 0U 0 :=
Vk
i=1 πViUi .
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 870
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
We state below Raz’s Parallel Repetition Theorem along with the recent improvements (and simplifi-
cations) by Holenstein and Rao.
Theorem 2.3 ([29, 18, 28]). There exists an absolute constant c > 0 such that for a 2P1R Game G with
val(G) = 1 − ε,
val(Gk ) ≤ (1 − ε 3 )ck .
For a Projection Game, the bound of (1 − ε 2 )ck holds.
2.2 Hardness of 3LIN
Our reduction is from the 3LIN problem over a finite field. For the proof of Theorem 1.2, we use Håstad’s
well-known hardness result for 3LIN [17]. For the proof of Theorem 1.4, we need a hardness result for
3LIN with very good completeness and we use a result of Khot and Ponnuswami [21].
Definition 2.4. For a prime power q, an instance (X, Φ) of 3LIN consists of a set of variables X over
Fq and a set of linear constraints Φ such that each constraint depends on exactly three variables. Let
OPT(X, Φ) denote the maximum fraction of constraints satisfied by any assignment.
Theorem 2.5 ([17]). For every constant η > 0 and a prime q, it is NP-hard to distinguish whether a
3LIN instance (X, Φ) over Fq has OPT(X, Φ) ≥ 1 − η or OPT(X, Φ) ≤ 1/q + η.
Theorem 2.6 ([21]). There is a reduction from a SAT instance Γ with size n to a 3LIN instance (X, Φ)
with size N over a field Fq of characteristic 2 such that:
2
• N and the running time of the reduction are bounded by 2O(log n) .
√
• If Γ is satisfiable, then OPT(X, Φ) ≥ 1 − 2−Ω( log N) .
1
• If Γ is unsatisfiable, then OPT(X, Φ) ≤ 1 − Ω .
log3 N
Remark 2.7. Theorem 2.6 is stated in [21] over the field F2 . It also holds for any extension field Fq since
in the YES Case, the good assignment is over F2 and in the NO Case, any assignment over Fq can be
mapped to an equally good assignment over F2 , e. g., by taking the last bit of every Fq -element.
Remark 2.8. We present the proof of Theorem 1.2 by constructing a PCP over the prime field Fq and the
Fourier analysis is over this field. For the proof of Theorem 1.4, we use the same PCP but over a field of
characteristic 2. We will omit the straightforward extension of our (Fourier) analysis to this case.
2.3 Hadamard code and Fourier analysis
Let q be a prime, ω := e2πi/q be the complex qth root of unity and Ω := {1, ω, . . . , ω q−1 }.
Definition 2.9. The Hadamard Code of α ∈ Fnq is defined as the table of values of the linear function
χα : Fnq → Ω where
∀x ∈ Fnq , χα (x) = ω α·x .
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 871
S UBHASH K HOT AND M ULI S AFRA
The vector space of all functions f : Fnq → C has an orthonormal basis {χα | α ∈ Fnq } where the inner
product between two functions f , g : Fnq → C is defined as (the expectation is over x uniformly distributed
in Fnq )
h i
h f , gi := E f (x)g(x) .
x
Hence, every f : Fnq → C can be expressed uniquely as
f = ∑ fb(α) χα .
α∈Fnq
The coefficients fb(α) ∈ C are called Fourier coefficients. These are defined by:
h i
fb(α) = h f , χα i = E f (x)χα (x) .
x
By Parseval’s identity, ∑α | fb(α)|2 = k f k22 = Ex [| f (x)|2 ]. In particular, for a function taking values in Ω,
the sum of squared absolute values of all its Fourier coefficients equals 1.
2.4 Quadratic Programming Problem
Definition 2.10. Given a real symmetric matrix A = {ai j }ni=1 with zero diagonal entries, the Quadratic
Programming Problem seeks to maximize ∑ni, j=1 ai j xi x j where ∀i, xi ∈ {−1, 1}. Let OPT(A) denote this
maximum (which is non-negative since the quadratic form is multi-linear and its maximum remains the
same if the variables are allowed to be in [−1, 1] and then {∀i, xi = 0} is a feasible solution).
It is important that the diagonal entries are zero as otherwise it is NP-hard to even decide whether
there is a {−1, 1}-valued assignment for which the quadratic form is non-negative. Given a graph
G(V = {1, . . . , n}, E), the maximum of the quadratic form
1 − xi x j
∑ −m
(i, j)∈E
2
is non-negative if and only if the graph has a cut with m edges and finding a maximum cut is NP-hard.
Theorem 1.3 follows directly from Theorem 1.4 and reducing the hard instance of 2P1R Game to the
Quadratic Programming Problem via Arora et al.’s reduction [2] below. Theorem 1.4 is proved using the
same PCP used to prove Theorem 1.2, but we need to use Theorem 2.6 as a starting point of the PCP
instead of Theorem 2.5.
Theorem 2.11 ([2]). There is a reduction from a Projection Game G(V, U, µ, R, S, {πVU }) to a Quadratic
Programming Problem instance A such that:
• The running time of the reduction and the number of variables of the instance A is polynomial in
|V| + |U| and 2|R| .
1
• If val(G) ≥ 1 − η, then OPT(A) ≥ 1 − η − .
|V| + |U|
• If val(G) ≤ ε, then OPT(A) ≤ O(ε).
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 872
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
2.5 Hellinger and statistical distance
The squared Hellinger distance between distributions D1 and D2 over a discrete probability space A is
1 p p 2 p
H 2 (D1 , D2 ) := ∑ D 1 (a) − D 2 (a) = 1 − ∑ D1 (a)D2 (a) .
2 a∈A a∈A
It is clear that 1 − H 2 (·, ·) is multiplicative for product distributions Dk1 , Dk2 on space Ak , i. e.,
1 − H 2 (Dk1 , Dk2 ) = (1 − H 2 (D1 , D2 ))k .
The statistical distance between D1 and D2 is:
1
∆(D1 , D2 ) := ∑ |D1 (a) − D2 (a)| .
2 a∈A
We have the standard inequality:
√
Lemma 2.12 ([27]). H 2 (D1 , D2 ) ≤ ∆(D1 , D2 ) ≤ 2 · H(D1 , D2 ) .
3 The Outer PCP
In this section, we describe our Outer PCP. For the ease of exposition, we do it in three stages, starting
with the standard Variable Versus Equation Game. We also prove the sub-code covering property. Let
(X, Φ) be an instance of the 3LIN problem over Fq given by Theorem 2.5 or Theorem 2.6.
3.1 The Variable Versus Equation Game
Consider the 2P1R Game where the verifier picks a random equation E ∈ Φ and then picks one of the
three variables x ∈ E. The first prover is sent the question E (i. e., the three variables appearing in E)
and the second prover is sent the question x. The provers answer with the Fq -values of all the variables
they receive. The verifier accepts if and only if the two provers agree on the variable x and moreover
the values given by the first prover satisfy the equation E. It is well-known and easy to check that if
OPT(X, Φ) = 1 − ε, then the value of the game is 1 − ε/3.
3.2 The Basic 2P1R Game
We now slightly modify the Variable Versus Equation Game and call it the Basic 2P1R Game (think of β
as small):
• The verifier picks an equation E ∈ Φ at random. Let x, y, z ∈ X be the variables in E.
• The first prover is sent the equation E.
• The second prover is sent the equation E with probability 1 − β and one of the three variables x, y, z
with probability β /3 each.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 873
S UBHASH K HOT AND M ULI S AFRA
• The provers answer with the values of all the variables they receive.
• The verifier accepts if and only if the two provers agree on the values of the variables and moreover
the values given by the first prover satisfy the equation.
Assume that OPT(X, Φ) = 1 − ε. The value of the game is at least 1 − ε since the provers may
stick to a (1 − ε)-satisfying assignment to (X, Φ) and in that case, the verifier may reject only when the
equation E is not satisfied.
On the other hand, the value of the game is at most 1 − Ω(εβ ) since with probability β , the second
prover receives exactly one variable and the variable versus equation game is played.
3.3 The Final 2P1R Game (Outer PCP)
The Outer PCP is now obtained as the k-wise repetition applied to the Basic 2P1R Game. Specifically:
• The verifier picks equations E1 , . . . , Ek ∈ Φ at random. Let V denote the set of 3k variables
appearing in these equations.
• The question V is sent to the first prover.
• Let U ⊆ V be chosen by including independently for each 1 ≤ i ≤ k, all three variables in equation
Ei with probability 1 − β and one of the three variables in equation Ei with probability β /3 each.
The question U is sent to the second prover.
• The provers answer with the values of all the variables they receive.
• The verifier accepts if and only if the two provers agree on the values of the variables in U and
moreover the values given by the first prover satisfy all the k equations E1 , . . . , Ek .
Assume again that OPT(X, Φ) = 1 − ε. The value of the game is at least 1 − εk since the provers
may stick to a (1 − ε)-satisfying assignment to (X, Φ) and in that case, the verifier may reject only when
at least one equation Ei is not satisfied.
On the other hand, we observe that the value of the game is at most (1 − Ω(ε 2 ))Ω(β k) . As noted before,
the value of the Basic Game is 1 − Ω(εβ ) and if we apply the parallel repetition theorem (Theorem 2.3)
directly, we end up with an upper bound of (1 − Ω(ε 2 β 2 ))Ω(k) . This bound is not good enough for us
and we get the better bound as follows. Call a coordinate useful if the second prover receives a single
variable, i. e., the standard Variable Versus Equation Game is played. The expected number of useful
coordinates is β k. Hence the probability that less than β k/2 coordinates are useful is at most 2−Ω(β k) and
may be ignored in comparison to the desired bound. The repeated game restricted to the question pairs
where at least β k/2 coordinates are useful can be thought of as a convex combination of sub-games, each
sub-game being the standard Variable Versus Equation Game repeated at least β k/2 times. Each such
sub-game has value at most (1 − Ω(ε 2 ))Ω(β k) and hence so does the overall repeated game.
We note that the k equations chosen by the verifier in the first step are disjoint (i. e., do not share
variables) with high probability and we make this assumption in all that follows.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 874
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
3.4 Sub-code covering property
Fix a question (E1 , . . . , Ek ) to the first prover in the Outer PCP and let V denote the set of variables
{x1 , . . . , x3k } in these equations. The question to the second prover is a subset U ⊆ V where independently
for each 1 ≤ i ≤ k, all three variables x3(i−1)+1 , x3(i−1)+2 , x3i are included in U with probability 1 − β and
exactly one of the three variables is included with probability β /3 each. Consider two distributions on
FVq = F3k q :
• Distribution D is uniform on FVq .
• Distribution D0 is obtained by picking a random question U ⊆ V to the second prover (as described
above), picking a string in FUq uniformly at random, and then “pulling up” this string to FVq by
inserting 0 at positions in V \U.
√
Lemma 3.1. The statistical distance ∆(D, D0 ) is upper bounded by O( k · qβ ).
Proof. We will bound the squared Hellinger distance on one coordinate, then use the multiplicativity of
the squared Hellinger distance for product distribution, and then upper bound the statistical distance in
terms of the Hellinger distance.
Let Q denote the uniform distribution on Fq and (Q, Q, Q) denote its three independent copies. On
any single coordinate 1 ≤ j ≤ k, note that D j is same as the distribution (Q, Q, Q) whereas D0j can be
written as:
β β β
D0j = (1 − β ) · (Q, Q, Q) + · (Q, 0, 0) + · (0, Q, 0) + · (0, 0, Q) .
3 3 3
The total probability mass attached by D j to triples in F3q where the number of non-zero entries is three,
two, one, and zero respectively is:
(q − 1)3 3(q − 1)2 3(q − 1) 1
p3 = 3
, p 2 = 3
, p1 = 3
, p0 = 3 .
q q q q
Similarly, the total probability mass attached by D0j to triples in F3q where the number of non-zero entries
is three, two, one, and zero respectively is:
(q − 1)3 0 3(q − 1)2 0 3(q − 1) q−1 0 1 1
p03 = (1 − β ) , p2 = (1 − β ) , p1 = (1 − β ) +β , p0 = (1 − β ) 3 + β .
q3 q3 q3 q q q
Hence
q q q q
1 − H 2 (D j , D0j ) = p3 p03 + p2 p02 + p1 p01 + p0 p00
(q − 1)3 p 3(q − 1)2 p
= 1 − β + 1−β
q3 q3
s 2
3(q − 1) q 1
q
+ 1 + − 1 β + 1 + (q2 − 1)β
q3 3 q3
≥ 1 − O(β 2 q2 ) ,
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 875
S UBHASH K HOT AND M ULI S AFRA
where all the square roots are estimated using
√ x
1 + x ≥ 1 + − x2
2
for x ∈ [−1/2, 1/2] and q2 β 1/2 (as will be the case). Thus the expression is lower bounded by
a0 + a1 β + a2 β 2 where it is easily checked that a0 = 1 and |a2 | = O(β 2 q2 ). The main point is that the
coefficient a1 vanishes. Indeed, a1 equals
(q − 1)3 3(q − 1)2 3(q − 1)
2
1 q 1 2
− − + · − 1 + 3 · (q − 1) = 0 .
2 q3 q3 q3 3 q
By multiplicativity of the squared Hellinger distance, we have
1 − H 2 (D, D0 ) = (1 − H 2 (D j , D0j ))k ≥ (1 − O(β 2 q2 ))k ≥ 1 − O(β 2 q2 k) .
√ √
Finally ∆(D, D0 ) ≤ 2 · H(D, D0 ) ≤ O( k · qβ ).
3.5 The choice of parameters
Let OPT(X, Φ) = 1 − ε where (X, Φ) is a NO instance of 3LIN given by Theorem 2.5 or Theorem 2.6.
• In Theorem 2.5, OPT(X, Φ) is close to 1/q and hence ε = Ω(1).
• In Theorem 2.6, OPT(X, Φ) ≤ 1 − Ω(1/log3 N) where N is the size of the 3LIN instance and hence
ε = ε(N) = Ω(1/log3 N).
The parameters will be chosen so that for a large enough constant C,
• The soundness of the Outer PCP, which is at most (1 − Ω(ε 2 ))−Ω(β k) , is at most 1/qC .
1
• ∆(D, D0 ) ≤ .
Cq2
Using Lemma 3.1, it suffices to choose
C∗3 q6 log2 q ε2
k= and β=
ε4 C∗2 · q6 · log q
for a large enough constant C∗ .
4 The Inner PCP
In this section, we describe our Inner PCP. We first analyze a test that we call Gowers Test, which is then
used to analyze the actual Inner PCP presented in Section 4.3. We begin with some notation and a simple
lemma.
Let ω := e2πi/q be the complex qth root of unity and Ω := {1, ω, . . . , ω q−1 }. For f , g : Fmq → Ω, let
AGR( f , g) denote the agreement between the two functions, i. e., the fraction of points on which they agree.
Let fi denote the function fi (x) := f (x)i . Note that for z ∈ Ω, the expression (1 + z + z2 + · · · + zq−1 )/q
equals 1 if z = 1 and 0 otherwise.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 876
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
Lemma 4.1. If f : Fmq → Ω is a function such that for some linear function χα , AGR( f , χα ) ≥ 1/q + δ .
q−1 b
Then ∑ j=1f j ( jα) ≥ qδ .
Proof. The lemma follows by noting that:
" #
1 q−1
AGR( f , χα ) = E
x q
∑ ( f (x)χα (x)) j
j=0
1 1 q−1 h i
= + ∑ E f j (x)χ jα (x)
q q j=1 x
1 1 q−1 b
= + ∑ f j ( jα) .
q q j=1
4.1 The Gowers test
For a function f : Fm
q → C, the Gowers Uniformity Norm U2 [15] is defined as
h i
kU2 ( f )k4 := E f (x) f (x + y) f (x + z) f (x + y + z) .
x,y,z
We will study the probability that a function f : Fm
q → Ω passes the test
f (x) f (x + y) f (x + z) f (x + y + z) = 1 ,
for a random choice of x, y, z. It is thus natural to name the test as the Gowers Test. It will be more
convenient for us to think of the test equivalently as
Gowers Test : f (x) f (y) f (z) f (−x + y + z) = 1 .
Lemma 4.2. Let f : Fm
q → Ω be a function. Then the acceptance probability of the Gowers Test is:
h i 1 1 q−1 4
Pr f (x) f (y) f (z) f (−x + y + z) = 1 = + ∑ ∑ fbj ( jα) .
x,y,z q q j=1 α
Proof. The acceptance probability can be expressed as
1 1 q−1 h i
+ ∑ E ( f (x) f (y) f (z) f (−x + y + z)) j
q q j=1
1 1 q−1
= + ∑ ∑ b f j (α) b
f j (φ ) b
f j (ψ) b
f j (γ) E χα−γ (x)χ−φ +γ (y)χ−ψ+γ (z)
q q j=1 α,φ ,ψ,γ
1 1 q−1 4
= + ∑ ∑ fbj (α) ,
q q j=1 α
noting that the expectation vanishes unless α = φ = ψ = γ. We can replace α by jα without changing
the summation.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 877
S UBHASH K HOT AND M ULI S AFRA
4.2 The Gowers test with side conditions
At the Inner PCP level, we need to check not only that a function f is linear, i. e., f = χα for some α, but
also that α itself satisfies a given set of linear constraints. We call these as side conditions and modify the
Gowers Test so as to incorporate these side conditions (and henceforth Gowers Test refers to one with
side conditions incorporated).
Given:
• A function f : Fm
q → Ω.
• Side conditions hi · x = bi , i = 1, . . . , k where hi ∈ Fm k
q , bi ∈ Fq . Assume that {hi }i=1 are linearly
independent and H is their linear span.
The Test:
• Pick x, y, z ∈ Fm
q at random.
• Pick a = (a1 , . . . , ak ) ∈ Fkq at random and let h = ∑ki=1 ai hi and a · b := ∑ki=1 ai bi .
• Accept if and only if
f (x) f (y) f (z) f (−x + y + z + h) = ω a·b .
Lemma 4.3. The following hold:
1. The Gowers Test always passes with probability at least 1/q.
2. If the Gowers Test passes with probability at least 1/q + δ , then there exists √ 1 ≤ j ≤ q − 1 and
m
α ∈ Fq that respects the side conditions (i. e., ∀i, α · hi = bi ) and | f j ( jα)| ≥ δ .
b
3. If f has agreement 1/q + δ with a linear function χα that respects the side conditions (i. e.,
∀i, α · hi = bi ), then f passes the Gowers Test with probability at least 1/q + δ 4 .
Proof. The acceptance probability of the Gowers Test with side conditions is:
1 1 q−1 h i
+ ∑ E ( f (x) f (y) f (z) f (−x + y + z + h)) j ω − ja·b
q q j=1
1 1 q−1 h i
f j (γ) E χα−γ (x)χ−φ +γ (y)χ−ψ+γ (z) E χγ (h)ω − ja·b
= + ∑ ∑ b f j (φ ) b
f j (α) b f j (ψ) b
q q j=1 α,φ ,ψ,γ a
1 1 q−1 4 h k i
= + ∑ ∑ fbj (α) · E ω ∑i=1 ai (α·hi − jbi )
q q j=1 α a
1 1 q−1 4
= + ∑ ∑ fbj (α)
q q j=1 α|∀i,α·h = jb i i
q−1 4
1 1
= + ∑ ∑ fbj ( jα) .
q q j=1 α|∀i,α·h =b i i
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 878
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
The first conclusion is immediate. The second uses the fact that the sum of squared absolute values of
Fourier coefficients of f j is 1. The third follows in conjunction with Lemma 4.1 and convexity of the
function x4 .
4.3 The Point-Subspace test with side conditions (Inner PCP)
Given:
• A function f : Fnq → Ω.
• Side conditions hi · x = bi , i = 1, . . . , k. Assume that {hi }ki=1 are linearly independent and H is their
linear span.
• A table {T(W ) | W ∈ C} where C denotes the class of k + 6 dimensional subspaces of the form
W = D ⊕ H for a 6-dimensional subspace D of Fnq such that D ∩ H = {0}. The entry T(W ) is a
linear function χ : W → Ω that respects the side conditions, i. e.,
χ(x + y) = χ(x) · χ(y) and χ(x + hi ) = χ(x) · ω bi ∀x, y ∈ W, i = 1, . . . , k .
The Test:
1. Pick a random W ∈ C and let T(W ) be the linear function on W .
2. Pick a random w ∈ W .
3. Accept if and only if f (w) = T(W )(w).
4.3.1 Completeness
Suppose f : Fnq → Ω is linear that respects the side conditions, i. e.,
f (x + y) = f (x) · f (y) and f (x + hi ) = f (x) · ω bi ∀x, y ∈ Fnq , i = 1, . . . , k .
Then letting T(W ) to be the restriction f |W , the point-subspace test passes with probability 1.
4.3.2 Soundness
Lemma 4.4. If the point-subspace test passes with probability 3/q then there exists 1 ≤ j ≤ q − 1 and
α ∈ Fnq that respects the side conditions (i. e., ∀i, α · hi = bi ) and | fbj ( jα)| ≥ 1/q2 .
Proof. Assume that the point-subspace test passes with probability 1/q + δ where δ ≥ 2/q. This means
that:
E [AGR ( f |W , T(W ))] = 1/q + δ .
W
By Lemma 4.3(1,3) and using convexity of the function x4 , we conclude that
E [Pr [ f |W passes Gowers Test]] ≥ 1/q + δ 4 . (4.1)
W
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 879
S UBHASH K HOT AND M ULI S AFRA
Now let us consider the probability that f passes the Gowers Test. The Gowers Test picks three points
x, y, z independently (from the global space Fnq ). Let ⊥ be the event that span(x, y, z, H) has dimension
k + 3 and let Γ be the set of all such triples (x, y, z). Conditional on ⊥ happening, the Gowers Test picks a
triple in Γ uniformly at random. An alternate way of picking a triple in Γ uniformly at random is to pick
a subspace W ∈ C and then pick (x, y, z) ∈ W 3 conditional on the event that span(x, y, z, H) has dimension
k + 3. Let ⊥(W ) be the event that span(x, y, z, H) has dimension k + 3 when x, y, z ∈ W are picked at
random. Thus:
Pr [ f passes Gowers Test | ⊥] = E Pr [ f |W passes Gowers Test | ⊥(W )]
W
≥ E Pr [ f |W passes Gowers Test] − Pr[¬⊥(W )]
W
3
≥ E Pr [ f |W passes Gowers Test] − 4
W q
1 3 1 2
≥ +δ4 − 4 ≥ + 4 ,
q q q q
where we used Pr[¬⊥(W )] ≤ 3/q4 and δ ≥ 2/q. Also, noting that
3
Pr[⊥] ≥ 1 − ,
qn−k−2
we get that
1 1
Pr [ f passes Gowers Test] ≥ + .
q q4
It follows now from Lemma 4.3(2) that there exists 1 ≤ j ≤ q − 1 and α such that ∀i, α · hi = bi and
| fbj ( jα)| ≥ 1/q2 .
5 The composed PCP
We now describe the composed PCP and prove Theorem 1.2. The Outer PCP is constructed from a
3LIN instance (X, Φ) as described in Section 3. The 3LIN instance is either (1 − η)-satisfiable or at
most (1 − ε)-satisfiable as per Theorem 2.5 or Theorem 2.6. The various parameters are chosen as in
Section 3.5.
The verifier in the composed PCP expects the proof to contain, for every question V to the first prover,
two tables LV and TV .
The tables LV The table LV gives the Hadamard code of the assignment to V . Concretely, let
{x1 , . . . , x3k } be the variables in V and σ : X → Fq be the global assignment that is supposed to be
an almost satisfying assignment to (X, Φ). The verifier expects, for the question V , the table of values of
the linear function LV : FVq = F3k q → Ω where
3k
LV (y) = ω ∑i=1 yi σ (xi ) .
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 880
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
Note that for every question U to the second prover, a table LU that gives the Hadamard code of the
assignment to U may be expected as well. However if U ⊆ V , then the table LU is contained in the table
LV . Specifically, for any z ∈ FUq , let z↑ denote the vector obtained by extending z to a vector in FVq be
inserting zeroes at the positions in V \U. Then
3k ↑
LU (z) = ω ∑i:xi ∈U zi σ (xi ) = ω ∑i=1 zi σ (xi ) = LV (z↑ ) .
Thus there is no need to have separate LU tables; we do however think of these as virtual tables. Whenever
there are questions V,V 0 to the first prover such that U ⊆ V ∩V 0 , the table LU is contained in both the
tables LV and LV 0 . We identify the locations in these two tables that correspond to the same location in
the (virtual) LU table.
The tables TV Let V be a question to the first prover that consists of equations (i. e., side conditions)
{hi · x = bi }ki=1 , the ith equation depending only on the variables (x3(i−1)+1 , x3(i−1)+2 , x3i ). Except with a
negligible probability (that we may ignore) over the choice of V , the k equations are disjoint (i. e., do
not share variables). Thus the vectors hi are linearly independent and let H be their linear span. The
table TV contains, for every k + 6 dimensional subspace W ⊆ FVq such that H ⊆ W , a linear function
TV (W ) : W → Ω that respects the side conditions.
The PCP verifier The verifier picks a random question V to the first prover in the Outer PCP. Let
{hi · x = bi }ki=1 be the side conditions and H be the linear span of vectors {hi }ki=1 . Let LV : FVq → Ω and
TV be the associated tables. The verifier picks a random k + 6 dimensional subspace W , H ⊆ W ⊆ FVq ,
and a random point w ∈ W . The verifier accepts if and only if
LV (w) = TV (W )(w) .
5.1 Completeness
Let σ : X → Fq be a global assignment that satisfies 1 − η fraction of equations. The table LV is the
Hadamard code (i. e., linear function) of the assignment σ restricted to V . The table TV gives, for every
subspace W , the linear function TV (W ) = LV |W . The test may fail only when there is some equation in V
that is not satisfied by σ . This happens with probability at most ηk.
5.2 Soundness
Assume on the contrary that the test accepts with probability 4/q. By an averaging argument, for at
least 1/q fraction of the questions V , the test accepts with probability at least 3/q. Fix any such good
V . By the analysis of the Inner PCP, Lemma 4.4, it follows that there exists 1 ≤ j ≤ q − 1 such that for
f := LV , there is a Fourier coefficient | b
f j ( jα)| ≥ 1/q2 and α respects the side conditions. Note that for
the uniform distribution D on FVq ,
h i
f j ( jα) = E
b f j (x)χ jα (x) .
x∈D
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 881
S UBHASH K HOT AND M ULI S AFRA
By the sub-code covering property, Section 3.5, it follows that for some error parameter e, |e| ≤ 1/(Cq2 ),
h i
f j ( jα) = E 0 f j (x)χ jα (x) + e
b
x∈D
" #
h i
= E E f j (y↑ )χ jα (y↑ ) +e
U y∈FU
q
" #
h i
= E E f j |U (y)χ jα↓ (y) +e
U y∈FU
q
h i
= E df j |U ( jα↓ ) + e ,
U
where f j |U denotes the restriction of f j to FUq ⊆ FVq and α↓ denotes the vector obtaining by dropping
coordinates of α in V \U. It follows that
h i 1 1 1
E f j |U ( jα↓ )
d ≥ |b
f j ( jα)| − |e| ≥ 2
− 2 ≥ 2.
U q Cq 2q
Thus, with probability at least 1/(4q2 ) over the choice of U (for the fixed good V ; call such (V,U) a good
pair),
1
f j |U ( jα↓ ) ≥ 2 .
d
4q
Note also that f |U = g = LU which is the supposed (virtual) Hadamard code for an assignment to U and
f j |U = g j .
Now we derive strategies for the provers in the Outer PCP as follows: the first prover, on receiving a
question V , considers the function f = LV , lists all α such that for some 1 ≤ j ≤ q − 1, | b
f j ( jα)| ≥ 1/q2
and α respects the side conditions, and then outputs a random element from the list. The list size is
bounded by q5 . The second prover, on receiving a question U, considers the function g = LU , lists all γ
such that for some 1 ≤ j ≤ q − 1, |gbj ( jγ)| ≥ 1/(4q2 ), and outputs a random element from the list. The
list size is bounded by 16q5 . The analysis above shows that when (V,U) is a good pair, there are α and
α↓ = γ in the lists for V and U respectively and α respects the side conditions. This and the bound on the
list sizes shows that with probability at least
1 1 1 1
· 2· 5· ,
q 4q q 16q5
the provers succeed. This is a contradiction since the soundness of the Outer PCP is at most 1/qC for a
large constant C as in Section 3.5.
6 Proofs of Theorem 1.4 and Theorem 1.3
Now we prove Theorem 1.4. It directly implies Theorem 1.3 using the reduction from 2P1R Game to
Quadratic Programming Problem as in Theorem 2.11 (one sets q = (log n)O(1/ε) ).
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 882
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
To prove Theorem 1.4, we use the same composed PCP as in Section 5, except that the 3LIN instance
from Theorem 2.6 is used as a starting point. A minor issue is that we presented our entire PCP for a
prime field Fq whereas now we need a PCP over a field of characteristic 2. We omit the straightforward
extension of our analysis to this case. Along with the setting of parameters in Section 3.5, we get a
reduction from a 3LIN instance (with the field Fq of characteristic 2) to a 2P1R Game G such that:
• The provers have q6 answers.
• The size of the 2P1R Game is at most qO(k) N k if the 3LIN instance has size (i. e., number of
equations) N.
• If the 3LIN instance is (1 − η)-satisfiable, then the value of the game is at least 1 − ηk.
• If the 3LIN instance is at most (1 − ε)-satisfiable, then the value of the game is at most 4/q.
2
The 3LIN instance from Theorem 2.6 has instance size N = 2O(log n) where n is the size of the starting
SAT instance. We have
√
−Ω( log N) 1
η = η(N) ≤ 2 and ε = ε(N) ≥ Ω .
log3 N
As noted in Section 3.5, it suffices to have
C∗3 q6 log2 q ε2
k= and β = .
ε4 C∗2 · q6 · log q
The soundness parameter of the 2P1R Game is 4/q as required. The completeness parameter is
1 − ηk with k = O(q6 log2 q log24 n) and η = n−Ω(1) . The size of the 2P1R Game is at most qO(k) N k
2 24 6 2
which is 2O((log n+log q) log n·q log q) as stated.
7 Acknowledgement
We thank Dana Moshkovitz and Ran Raz for a discussion about the sub-code covering property (in a
different context). Thanks to both for pointing us to their analysis of the point versus 2-dimensional
subspace test. We also thank Preyas Popat for pointing out a flaw in an earlier version of the paper. Many
thanks to anonymous referees for suggesting several improvements to the presentation.
References
[1] S ANJEEV A RORA , L ÁSZLÓ BABAI , JACQUES S TERN , AND E LIZABETH Z. S WEEDYK: The
hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput.
System Sci., 54(2):317–331, 1997. Preliminary version in FOCS’93. [doi:10.1006/jcss.1997.1472]
864
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 883
S UBHASH K HOT AND M ULI S AFRA
[2] S ANJEEV A RORA , E LI B ERGER , E LAD H AZAN , G UY K INDLER , AND M ULI S AFRA: On non-
approximability for quadratic programs. In Proc. 46th FOCS, pp. 206–215. IEEE Comp. Soc. Press,
2005. See also at ECCC. [doi:10.1109/SFCS.2005.57] 865, 872
[3] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. Preliminary version in FOCS’92. See also at ECCC. [doi:10.1145/278298.278306] 864, 866
[4] S ANJEEV A RORA AND S HMUEL S AFRA: Probabilistic checking of proofs: A new characterization
of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]
864, 865, 866, 869
[5] S ANJEEV A RORA AND M ADHU S UDAN: Improved low-degree testing and its applications. Combi-
natorica, 23(3):365–426, 2003. Preliminary version in STOC’97. [doi:10.1007/s00493-003-0025-0]
865, 866, 869
[6] M IHIR B ELLARE , O DED G OLDREICH , AND M ADHU S UDAN: Free bits, PCPs, and
nonapproximability—towards tight results. SIAM J. Comput., 27(3):804–915, 1998. Prelimi-
nary version in FOCS’95. See also at ECCC. [doi:10.1137/S0097539796302531] 864, 866
[7] M IHIR B ELLARE , S HAFI G OLDWASSER , C ARSTEN L UND , AND A. RUSSELL: Efficient proba-
bilistically checkable proofs and applications to approximations. In Proc. 25th STOC, pp. 294–304.
ACM Press, 1993. See correction to abstract in STOC’94. [doi:10.1145/167088.167174] 870
[8] M ANUEL B LUM , M ICHAEL L UBY, AND RONITT RUBINFELD: Self-testing/correcting with appli-
cations to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version
in STOC’90. [doi:10.1016/0022-0000(93)90044-W] 866
[9] S IU O N C HAN: Approximation resistance from pairwise independent subgroups. In Proc. 45th
STOC, pp. 447–456. ACM Press, 2013. See also at ECCC. [doi:10.1145/2488608.2488665] 865,
869
[10] M OSES C HARIKAR AND A NTHONY W IRTH: Maximizing quadratic programs: extending
Grothendieck’s inequality. In Proc. 45th FOCS, pp. 54–60. IEEE Comp. Soc. Press, 2004.
[doi:10.1109/FOCS.2004.39] 865
[11] A NNE C ONDON: The complexity of the max word problem and the power of one-way interactive
proof systems. Comput. Complexity, 3(3):292–305, 1993. Preliminary version in STACS’91.
[doi:10.1007/BF01271372] 864
[12] L ARS E NGEBRETSEN AND J ONAS H OLMERIN: More efficient queries in PCPs for NP and
improved approximation hardness of maximum CSP. Random Structures & Algorithms, 33(4):497–
514, 2008. Preliminary version in STACS’05. [doi:10.1002/rsa.20226] 869
[13] U RIEL F EIGE: A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998.
Preliminary version in STOC’96. [doi:10.1145/285055.285059] 864
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 884
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
[14] U RIEL F EIGE , S HAFI G OLDWASSER , L ÁSZLÓ L OVÁSZ , S HMUEL S AFRA , AND M ARIO S ZEGEDY:
Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996.
Preliminary version in FOCS’91. [doi:10.1145/226643.226652] 864, 865, 866
[15] T IMOTHY G OWERS: A new proof of Szemerédi’s theorem for progressions of length four. Geomet-
ric and Functional Analysis, 8(3):529–551, 1998. [doi:10.1007/s000390050065] 877
[16] J OHAN H ÅSTAD: Clique is hard to approximate within n1−ε . Acta Mathematica, 182(1):105–142,
1999. Preliminary version in FOCS’96. [doi:10.1007/BF02392825] 864, 866
[17] J OHAN H ÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Prelimi-
nary version in STOC’97. [doi:10.1145/502090.502098] 864, 866, 867, 871
[18] T HOMAS H OLENSTEIN: Parallel repetition: Simplification and the no-signaling
case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07.
[doi:10.4086/toc.2009.v005a008] 864, 871
[19] S UBHASH K HOT: Improved inapproximability results for MaxClique, chromatic number and
approximate graph coloring. In Proc. 42nd FOCS, pp. 600–609. IEEE Comp. Soc. Press, 2001.
[doi:10.1109/SFCS.2001.959936] 866
[20] S UBHASH K HOT, G UY K INDLER , E LCHANAN M OSSEL , AND RYAN O’D ONNELL: Optimal
inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–
357, 2007. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]
866
[21] S UBHASH K HOT AND A SHOK K UMAR P ONNUSWAMI: Better inapproximability results for max-
clique, chromatic number and Min-3Lin-Deletion. In Proc. 33th Internat. Colloq. on Automata, Lan-
guages and Programming (ICALP’06), pp. 226–237. Springer, 2006. [doi:10.1007/11786986_21]
871
[22] S UBHASH K HOT AND M ULI S AFRA: A two prover one round game with strong soundness. In
Proc. 52nd FOCS, pp. 648–657. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.62] 863
[23] A LEXANDRE M EGRETSKI: Relaxation of quadratic programs in operator theory and system
analysis. In Proc. International Workshop on Operator Theory and Applications (IWOTA’00), pp.
365–392. Springer, 2000. [doi:10.1007/978-3-0348-8362-7_15] 865
[24] DANA M OSHKOVITZ: The projection games conjecture and the NP-hardness of ln n-approximating
set-cover. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinato-
rial Optimization Problems (APPROX’12), pp. 276–287. Springer, 2012. See also at ECCC.
[doi:10.1007/978-3-642-32512-0_24] 870
[25] DANA M OSHKOVITZ AND R AN R AZ: Two-query PCP with subconstant error. J. ACM, 57(5):29:1–
29:29, 2010. Preliminary version in FOCS’08. See also at ECCC. [doi:10.1145/1754399.1754402]
869
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 885
S UBHASH K HOT AND M ULI S AFRA
[26] A RKADI N EMIROVSKI , K EES ROOS , AND TAMÁS T ERLAKY: On maximization of quadratic form
over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463–473,
1999. [doi:10.1007/s101070050100] 865
[27] DAVID P OLLARD: A user’s guide to measure theoretic probability. Cambridge Univ. Press, 2002.
CUP. 873
[28] A NUP R AO: Parallel repetition in projection games and a concentration bound. SIAM J. Comput.,
40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042] 864, 871
[29] R AN R AZ: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary
version in STOC’95. [doi:10.1137/S0097539795280895] 864, 871
[30] R AN R AZ AND S HMUEL S AFRA: A sub-constant error-probability low-degree test, and a sub-
constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM
Press, 1997. [doi:10.1145/258533.258641] 865, 866, 869
[31] A LEX S AMORODNITSKY AND L UCA T REVISAN: A PCP characterization of NP with op-
timal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000.
[doi:10.1145/335305.335329] 869
AUTHORS
Subhash Khot
Professor
New York University, New York, NY
khot cs nyu edu
http://www.cs.nyu.edu/~khot
Muli Safra
Professor
Tel Aviv University, Tel Aviv, Israel
safra tau ac il
http://www.tau.ac.il/~safra
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 886
A T WO -P ROVER O NE -ROUND G AME WITH S TRONG S OUNDNESS
ABOUT THE AUTHORS
S UBHASH K HOT is a Professor in the Computer Science Department at New York University.
He has a Ph. D. from Princeton University, completed in 2003 under the supervision of
Sanjeev Arora.
His teacher and mentor at Vyankatrao Highschool, Mr. Vaman G. Gogate played a
decisive role in directing his attention to mathematics. If not for Mr. Gogate’s guidance
and some fortuitous turn of events, the chance of someone from the remote town of
Ichalkaranji pursuing mathematical research was strictly nil. Subsequently, Mr. Gogate
also mentored Amit Deshpande and Raghav Kulkarni (CS theorists) and Abhijit Gadde
(string theorist). He is in touch with all his past students and continues to provide
guidance on all aspects of life.
M ULI S AFRA is a Professor of Computer Science at Tel Aviv University. He has a Ph. D.
from the Weizmann Institute, completed in 1990 under the supervision of Amir Pnueli.
He is one of the recipients of the 2001 Gödel Prize.
T HEORY OF C OMPUTING, Volume 9 (28), 2013, pp. 863–887 887