数理解析研究所講究録
第 1649 巻 2009 年 129-136

129

An Improvement of the Soundness of a 3-bit PCP
Naoki Kinoshita*

Suguru Tamaki*

kinoshita@kuis.kyoto-u.ac.jp

tamak@kuis.kyoto-u.ac.jp

Abstract

an approximate solution to an optimal solution is defined asfollowing:

Approximation algorithms have been studied to copewith computationally hard combinatorial problems such as
NP-hard problems, for which we cannot hope for exact
solutions efficiently. Approximation algorithms computefeasible solutions with some theoretically guaranteed quality in polynomial time. Probabilistically Checkable Proofs(PCPs) have been succeeded to show the limitation of suchapproximation algorithms, that is, how good approximate
solutions can be compared to optimal solution.
PCP is a mathematical model which probabilisticallyrecognizes a ceitain (especially NP) language by making
queries to a kind of oracle called a proof. There are some
important parameters which characterize PCPs. Completeness (soundness) is the maximum probability that a PCP accepts an input which is in (respectively, not in) . The number of queries to the proof and the adaptivity in queries, thatmeans a dependency between the queries, are also impoitant
aspects. In this paper, we study how small the soundness ofa PCP can be when it has perfect completeness and makes
non-adaptive three queries.
We can show better hardness of approximation of thetimization problem corresponding to a PCP if we can construct a PCP with smaller soundness. Khot and Saket obtained a PCP with soundness value, thatprobabilistically selects one of four tests and perform it to
the proof. We show that the soundness can be
0.73798 by optimizing the probability of selecting each test.
Here is an arbitrarily small constant. As a result of our
optimization, one of the four tests are shown to be unneces$L$$L$$oparrow$$\frac{20}{27}+\epsilon\simeq 0.74074$$\frac{16+\sqrt{6}}{25}+\epsilon\simeq$$\epsilon$

sary.

1

Kazuo Iwama*

iwama@kuis.kyoto-u.ac.jp

Introduction

Most natural optimization problems arising in application areas are NP-hard. It is widely believed that we needsuper-polynomial time to obtain optimal solutions for them.
Thus, Rom the perspective of practice, it is important toconsider approximation algorithms for obtaining approximate solutions that may not the same as but close to optimal
solutions. In approximation algorithms, to guarantee the ratio of the quality of an approximate solution to that of an
optimal solution is very important issue. The proximity of’Graduate School of Informatics, Kyoto University

approximation ratio $= \min\frac{qua1ityofapproximateso1ution}{qua1ityofoptima1so1ution}$

Here we consider maximization problems and assume thatthe value of the quality of a solution is positive, and $\min$ istaken over all the possible inputs for the algorithm. Hencethe approximation ratio is a value between to 1 and larger
value means better. The best possible approximation ratio of polynomial time algorithms differs according to eachproblem. Giving upper bounds on an approximation ratioof certain problem is an important theme in the study ofapproximation algorithms and is called the hardness of approximation or inapproximability.
$0$

A typical way to prove the hardness of approximation is
the reduction Rom PCP. We consider a PCP that has perfectcompleteness, that means the completeness is 1, and makes
three non-adaptive queries to the proof. Perfect completeness means that all the inputs which should be accepted are
accepted with proper proofs. Non-adaptive means the content of every query is independent from any other queries.

We describe some previous results around 3-bit PCPs below. If we are allowed to loose perfect completeness, there
is a well-known PCP due to Hastad [6], that has completeness l-c, soundness
and makes non-adaptive queries,
Here, is an arbitrarily small constant. When assuming perfect completeness, Guruswami et al. [5] showed a PCP withsoundness
and adaptive queries. Above both results
are tight, that is, the PCP with smaller soundness always
looses the ability of recognizing NP languages. Therefore,
there is a trade-off between non-adaptiveness and perfectcompleteness of a PCP. For the PCP of this paper’s scope,
Khot and Saket [10] showed the current smallest soundness value
with perfect completeness and three nonadaptive queries. In this paper, we show that the soundness
can be improved to. There may be still a room
to improve the soundness as Zwick [13] conjectured thatthe soundness can be possibly improved to . Recently,
O’Donnell and Wu [11] showed that Zwick’s conjecture istme, i.e., the soundness can be achieved under Khot’s dto-l Conjecture [8] which is a stronger than standard $P\neq NP$
assumption.
$\frac{1}{2}+\epsilon$$\epsilon$$\}$$+\epsilon$$\frac{2}{2}07+\epsilon$$\frac{16+\sqrt{6}}{25}+\epsilon$$\epsilon 5$$\frac{5}{8}$130
2 Probabilistically Checkable Proofs
2.1

Definitions

A language class recognized by a PCP is defined as fol-

lows.

$G$

Definition 1. (Probabilistically Checkable Proof) A language is in a language class PCP $c,s[r(n), q(n)]$ if there
exists a polynomial time probabilistic Turing machine $Vs.t$.
given an input of size and a prvof
$L$

.

$x$

$n$

$\Pi,$$V$.

Accepts or rejects
quenes.

$x$

$V$

$\Pi$

$x$

-Soundness: If$x\not\in L$ ,for any proof
cepted by $V$ with probability at most .

$\Pi$. is ac$x$$s$

Parameters

$c,$

$s$

are called completeness and sound-ness respectively. To clarify whether the queries aredone adaptively or non-adaptively, we use the notation$aPCP$ , naPCP. The PCP is said to have perfect complete-ness if its completeness is 1. That is a desirable property
since we can reduce the soundness of such PCPs to arbitrarily small constant by repeating verification. In this smdy weonly consider PCPs with perfect completeness. As for the
power of PCPs, the following PCP Theorem is well known.

Theorem 2. (PCP Theorem, Arora et al.[l, 2]) NP

naPCPl,}$=$$[O(\log n), O(1)]$This theorem means that for an arbitrary NP language ,there is a PCP such that if a string is in , then it can bealways accepted by the PCP by giving a proper proof, andif is not in , then it cannot be accepted by the PCP withprobability more than by using any proof. Furthermore, it
shows that such PCPs need only constant number of queries
to the proofs regardless of input length. Inmitively, reducing the number of queries in PCP with keeping the same
soundness implies better inapproximability results.
$L$

$x$

$L$

$L$

$\frac{1}{2}$2.2 2 Prover 1 Round Games$\omega(G)$$\omega(G)=\max Pr[V(x)=Acc]A,B^{\cdot}$

The ratio of soundness and completeness of a PCP isclosely related to the approximability of a certain optimization problem. It gives upper bounds on the approximation
ratio achieved by polynomial time algorithms for the problem. Thus, a PCP with smaller soundness is desired to obtain better inapproximability results. Soundness represents
the probability that the PCP accepts an input which must
be rejected. Let us think of a PCP as a $2PlR$ game $G$ andconsider a new game where we perform the same game independently for times to the same input and accept if the
input is accepted by all games. In this case, the value of theentire game becomes, and if the completeness is 1
(or suff ciently close to 1), then the soundness can be madeexponentially (and thus arbitrarily) small w.r. . . However,notice that if we repeat the game independently, the game
becomes u-round game and the relation to the PCP does nothold any longer. To keep the correspondence to PCP, weposc a restriction that the verifier should scnd questions oftimes repetition at once. We write such a l-round gameand call a parallel repetition of a game. The value of thegamedoes not decrease as
in case of independently repeated games, but it also decreases exponentiallyw.r. . , as shown by Raz.
$u$$\omega(G)^{u}$$t$$P_{2}$

$A$

$u$

$u$

$G^{u}$$G^{u}$$t$$\omega(G)^{u}$$u$

Theorem 4. (ParaUel Repetition Theorem, Raz [12])Given a $2P1R$ game $G$ with soundness $s<1$ and answer
set of size , there exists a constant $s’<1$ which depends$s.t$.
$G’ su$ times parallel repetition
only onhas thesoundness $(s’)\#$ .
$d$$G^{u}$$s,$

The process of a PCP can be viewed as a game between
the prover who gives a proof and the verifier who verifies
the input by questioning to the prover. In other words, theprover tries to make verifier accept regardless of the input
and the verifier tries to accept only the correct input by detecting prover’s lies. We can think of PCP proofs as two
dynamic provers
andrather than a bit string. This
interpretation often makes the design of better PCPs easier. In this case, the provers answer to the verifier’s question obey their pre-determined strategies and $B$ respectively. They are not allowed to communicate each other nor$P_{1}$$P_{2}$

2.3 Parallel Repetition

Completeness: If $x\in L$ , there exists a proof
such that accepts with probability at least a
$V$

$A$

$x$

according to the result of thehas these two properties:-$x$

Deflnmon 3. (The value of a game $G$ ) Given a game $G$,
denote by $V(x)=$ Acc an event that the verifier accepts
the input according to the strategies and $B$ of provers
and . Then the value of the game $G$, denoted by,is defined as$P_{1}$

Uses $r(n)$ random bits and makes $q(n)$ bits of queries
to .
$\Pi$

1

know the question to another prover after the PCP verification process starts. We need such restrictions to assurethat the verification ability of the entire system does not increase since the proof changes ffom a static string to two
dynamic provers. Such games are called 2-prover l-roundgames ( $2PlR$ games). We define the value of a game asfollows.

Although we can decrease the soundness by parallel repetition, there is a drawback, that is, the number of query
bits also becomes times as the original game. Thus it cannot be used in a sffaightforward way to improve the soundness of the PCP. To construct PCPs with small number ofquery bits, we can use a technique of “composition”; wecan combine this parallel repeated games with arbiaarily
small soundness, called outer verifier, and another verifler
which uses small number of query bits, called inner verifier,to make soundness and number of queries small at the same
$u$

time.

131
2.4 Long Code

3.1

Although an outer verifier can have large number ofquery bits, an inner verifier is required to significantly reduce the number of query bits. To do so, encoding a proof
in some proper way is very helpful. Currently the most useful encoding way is the one introduced by Bellare et al. [3],The outer verifier used in Khot-Saket’s PCP is a tester
for satisfiability of a 3-SAT fonnula and its soundness is
reduced by parallel repetition. The following theorem about
the complexity of 3SAT is known.

called a Long Code.

Definition 5. (Long Code) Let$\{0,1\}\}$ . The long codeof an element$\mathcal{F}_{\Lambda t}=\{f|f$$x\in \mathcal{M}$a map as$A_{x}:\mathcal{F}_{\mathcal{M}}\mapsto\{0,1\}$Given an,:$\mathcal{M}\mapsto$

is defined by$A_{x}(f)=f(x)$.

bit input, Let $G$ be a corresponding $2PlR$$V$
makes total bits of queries toandand consider the parallel repetition. In,
the number of the queries made by the verifier becomes $Tu$ .
We would like to reduce it to some constant number independent of by encoding the provers’ strategies in someway. Let the set of answers in
be $\mathcal{M}=\{0,1\}^{Tu}$ . $V$
would like to decide whether the answer
from theprovers is in the subset
of answers which satisfy
the condition of acceptance. Now, deflne a function
as$n$game where the verifler$P_{1}$$T$$P_{2}$$G^{u}$$G^{u}$$u$$G^{u}$$x\in \mathcal{M}$$S\subseteq \mathcal{M}$$f_{S}$$f_{S}:\mathcal{M}\mapsto\{0,1\}$,$f_{S}(x)=\{\begin{array}{l}1(x\in S)0(x\not\in S)\end{array}$Outer Verifler

Theorem 7. ([9]) There exists an universal constant $c<1$
such that distinguishing that a 3-SAT formula is satisfi$\psi$able (YES instance) or no more than fraction of clauses
can be satisfied simultaneously by any assignment is NPhard. Moreover the above statement holds even when formulas have canonical property that every clause consistsof exactly three literals and every variable appears exactly
five times in them. We call a 3-SATformula with the above
properties a 3-SAT-5 instance.
$c$

The $2PlR$ game used here is constmcted by Khot [7]. We
denote by $V_{2PlR}$ the outer verifier explained here to distinguish it from the inner verifier which is of our interest for
improvement.
First, letbe Boolean variables andbe the clauses in a 3-SAT-5 instance . This
game is parametrized by $T$ and . We assume $T,$ $u\gg 1$
and these parameters can take arbitrarily large values independently. The verifier $V_{2PlR}$ chooses $Tu$ random clauses
from and let these clauses be $W=\{C_{1}, C_{2}, \ldots, C_{Tu}\}$ .
Let $W$ a question toandanswers an assignment tothe clauses in $W$ needed for to be satisfied. We describe
the set of possible satisfied assignments to $W$ by
andan answer ofby. Next $V_{2PlR}$ chooses a
subset of $W$ of size at random. We describe the subset by $S=\{C_{i_{1}}, C_{i_{2}}, \ldots, C_{i_{u}}\}$ and assume the order as$1\leq i_{1}<i_{2}<\cdots<i_{u}\leq Tu.$ Each clausecontains three variable and $V_{2PlR}$ chooses from each clause avariable. Let. Notethat $U$ is a family of variables and $(T-1)u$ clauses. $U$
is a question to the proverandanswers an assignment to the variables and clauses in $U$ needed for to besatisfied. We describe the set of these assignment by
and an answer ofby. Any assignmem to$W$ can be restricted toan assignment to $U$ and confirming such relation is the consistency test of $V_{2PlR}$ . Mapping:
represents the restriction Rom anassignment $W$ to $U$ and $V_{2PlR}$ accepts iff $\pi^{W,U}(\sigma)=\tau$ .
Here we describe the set of all possible questions tobyand toby . Obviously, if the fomiula is an
YES instance (satisfiable),andhave a strategy whichmakes $V_{2PlR}$ accept with probability 1. The strategy is thatfirst fix a satisfiable assignment to and both provers answer the exact assignment.
If is a NO instance (no more than fraction of clauses
can be satisfied by any assignment), by theorem 4, the following holds.
$\{x_{1}, x_{2}, \ldots\}$$\{C_{1}, C_{2}, \ldots\}$$\psi$$u$$\psi$

Then, we can check whether $x\in S$ or not by only 1 bit

query of. This gives an intuitive explanation for
reducing query bits by Long Code. Of course, the above 1
bit verification can be easily cheated by provers
and ’sstrategies of setting$A(f)=1$ . Thus $V$ is also required
to check whether the strategy of the provers satisfies thedefinition of a Long Code, that is, ヨ$A(f)=f(x)$ .
We can perform such a verification by using 3-bits, whichis the known smallest number for it, and we will focus onsuch 3-bits tests. Note that the size of a Long Codetosomeis calculated as$A_{x}(f_{S})$$P_{1}$$P_{2}$$\forall f,$$A$$x,\forall f,$$A_{x}$$x\in \mathcal{M}$$P_{1}$$P_{1}$$\phi$$\mathcal{M}_{W}$$\sigma\in \mathcal{M}_{W}$$P_{1}$$u$$C_{i_{j}}$$U=\{x_{i_{1}}, x_{i_{2}}, \ldots, x_{i_{u}}\}\cup(W\backslash S)$$x_{i_{j}}$$u$$P_{2}$$P_{2}$$\phi$$|A_{x}|=|\mathcal{F}_{\Lambda 4}|=2^{|\Lambda 4|}=2^{2^{Tu}}$$\mathcal{M}_{U}$It means that in, the domain size of the queries asked
by $V$ is represented bybits. Since both $T$ and are
constants that do not depend on input size , the size
$V$ canis also constant. Thus, in
perform queries toandin a constant time.
$G^{u}$$2^{2^{Tu}}$

$u$

$n$

$2^{2^{Tu}}$$G^{u},$$P_{1}$$P_{2}$$P_{2}$$\pi^{W,U}$$\mathcal{M}_{W}\mapsto \mathcal{M}_{U}$$P_{1}$$\mathcal{W}$

3 3-bit PCPTheorem 6. (Khot et al. [10]),$P_{2}$$\mathcal{U}$$\psi$$P_{1}$

We focus on non-adaptive 3-bit PCPs with perfect completeness. The construction due to Khot and Saket achieves
the current smallest soundness value, as presented in the restof this section.

$\forall\epsilon>0$$\tau\in \mathcal{M}_{U}$

NP

$=$

naPCP $1,ae+\epsilon[O(\log n), 3]$$\psi$$\psi$$c$

Theorem 8. If is NO instance, with any strategy,
andcannot make $V_{2PlR}$ accept with probability higher than
. Here is an universal constant.
$\psi$$P_{2}$In this section, we look inside their PCP construction.

$P_{2}$$c_{0}^{u}$$c_{0}$$P_{1}$

132
3.2 Biased Long Code

3.3.1

We review biased Long Code and its Fourier transformation used in the analysis of Khot-Saket’s PCP. In what
follows, we represent Boolean value of {true, false} by$\{-1,1\}$ instead of
1, . With such a notation, we canwrite exclusive-or of Boolean variables by arithmetic multiplication.
Biased long code has bias on the distribution of its index
function. Here,.
Let the bias $0<p<1$ and the function is selected forevery
to be $f(x)=-1$ with probability and$f(x)=1$ with probability $1-p$ . We denote this as $f\in R$
$0\}$

$\{$

$\mathcal{F}_{\mathcal{M}}=\{f|f :$f\in \mathcal{F}_{\Lambda 4}$\mathcal{M}\mapsto\{-1,1\}\}$$f$$x\in \mathcal{M}$$\mu_{p}(\mathcal{M})$$p$.

Fourier transformation is used for the analysis of tests
with long code. Biased case of Fourier analysis is known
for example in [4] and we need to choose appropriate orthonormal basis. The space of all tables:
forms adimensional real vector space and addition of
two tables
andis defined at each point as
$A$

Test

Test
checks the consistency between long codes$B$ .
The procedure of the test
is following.
$T_{1}$$W\in \mathcal{W}$For every$x\in \mathcal{M}$, a function$\phi_{x}$:$\mathcal{F}_{\lambda 4}\mapsto R$$A$$\mathcal{F}_{At_{U}}\mapsto$

$U$

$U$

2. Choose functions
independently.
3. For each...
.

$\{-1,1\}$$A_{2}$$A_{2}\rangle=E_{f\in\mu_{p}(\Lambda 4)}R[A_{1}(f)A_{2}(f)]$$U\in \mathcal{U}$$\mathcal{F}_{\mathcal{M}_{W}}\mapsto\{-1,1\}$$(A_{1}+A_{2})(f)=A_{1}(f)+A_{2}(f)$ .

$\langle A_{1},$and

1. According to the method of the verifier $V_{2PlR}$ , choose
random set
and its subset. The ver:ifler expect $B$ :and$\{-1,1\}$ to be the long codes corresponding to the assignments to $W$ and respectively. Let $\pi=\pi^{W,U}$ themapping from $W$ to .

$\mathcal{F}_{\mathcal{M}}\mapsto R$$f\in R\mu_{P}(\mathcal{M}_{U})$$y\in \mathcal{M}_{W}$

as

and

$g\in R\mu_{p}(\mathcal{M}_{W})$, choose a function $h$:$\mathcal{M}_{W}\mapsto$$f(\pi(y))=1\wedge g(y)=1arrow h(y)=1$$f(\pi(y))=1$ A $g(y)=-1arrow h(y)=-1$$f(\pi(y))=-1\wedge g(y)=1arrow h(y)=-1$$f(\pi(y))=-1\wedge g(y)=-1arrow$$h(y)=\{\begin{array}{ll}1 with prob.

Inner product in this space is defined as$A$$T_{1}$$2^{|\Lambda t|}$$A_{1}$$T_{1}$

q/p-1 with prob.

1-q/p\end{array}$

4. Accept iff $(A(f), B(g), B(h))\in S_{1}$ . Where$S_{1}=\{(1,1,1),$ $(1, -1, -1),$ $(-1,1, -1)$ ,.

$(-1, -1,1),$ $(-1, -1, -1)\}$is defined as

Let us consider the completeness of the test . Whenthe 3-SAT-5 formula is an YES instance, there exists a
strategy which makes the outer verifier $V_{2PlR}$ always accept. That is, fix one of the satisfiable assignment andanswer the queries of the verifier according to the assign$\pi(y)=x$ ofment. Pick some paits
the satisfiable assignment corresponding to $U$ and $W$ andlet them long codes
and $B$ . Due to the definition ofcode,$(A(f), B(g), B(h))=(f(x),g(y), h(y))=$the long$(f(\pi(y)), g(y), h(y))$ holds and now $(f, g, h)$ aoe chosen al$T_{1}$$\psi$$\phi_{x}(f)=\{\begin{array}{ll}-\sqrt{q}/p if f(x)=-1\sqrt{p}/q if f(x)=1\end{array}$

The orthonormal basis is represented as below. For every, define:
subsetas$\beta\subseteq \mathcal{M}$$\chi_{\beta}$$\mathcal{F}_{\mathcal{M}}\mapsto R$$\chi_{\beta}=\prod_{x\in\beta}\phi_{x}$.

$x\in \mathcal{M}_{U},$ $y\in \mathcal{M}_{W},$$A$

ways as,In above definition,holds and for any$\chi\{x\}=\phi_{x}$ holds. Hence every table can be represented as$x\in \mathcal{M}$$x\emptyset=1$$A= \sum_{\beta\subseteq \mathcal{M}}\hat{A}_{\beta}\chi_{\beta}$.

$\forall y\in \mathcal{M}_{W}$,$(f(\pi(y)), g(y),g(h))\in S_{1}$ ,so the PCP verifier always accept. Thus,

has perfectcompleteness.
Next, to consider the soundness of the test
, assume
the formula is a NO instance. We bound the acceptanceprobability of the verifier using Fourier analysis. Here thefollowing holds.
Lemma 9. ([10]) When $x,$ $y,$ $z\in\{-1,1\}$ , expression$T_{1}$$T_{1}$$\psi$

Hereas$\hat{A}_{\beta}$

is called a Fourier cocfficients, which is calculated$\hat{A}_{\beta}=\langle A,$

When the range of
Parseval’s identity.

$A$$\chi_{\beta}\rangle$

is $\{-1,1\},$.

$\sum_{\beta}\hat{A}_{\beta}^{2}=1$

holds by$\frac{5-x-y-z+xy+xz+yz+3xyz}{8}$has value 1 only when $(x,y, z)\in S_{1}$ and otherwise.
Using above lemma, the acceptance probability of theverifier can be represented by$0$

3.3 Test of the Verifier
The PCP consists of four tests. In this section, we describe the behavior and some pait of the analysis of the tests.
Each test is performed with probability defined later. We
define the bias on queries by$q=1-p$ andparameter $\epsilon>0$ is assumed to be taken arbitrarily small.
Also, letand is taken sufficiently large.
$p= \frac{1}{2}+\epsilon,$$T=\urcorner_{\epsilon}1$$u$$Pr[Acc]=E_{W,U,f,g,h}[\frac{1}{8}(5-A(f)-B(g)-B(h)$$+A(f)B(g)+A(f)B(h)$$+B(g)B(h)+3A(f)B(g)B(h))]$ .

133
We use Fourier transfomi on the above expression andbound all terms, then we have$\mathcal{M}_{W}\mapsto\{-1,1\}$

as following.

$(g_{1}(y), g_{2}(y),g_{3}(y))$$Pr[Acc]$$\leq E_{W,U}[\frac{5-\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}+2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}_{\emptyset}^{2}+3\hat{A}_{\emptyset}\hat{B}_{\emptyset}^{2}}{8}]+O(\epsilon)$

3.3.2 Test.

$=\{\begin{array}{l}(-1,1,1), (1, -1,1), (1,1, -1)with each prob.

$T_{2}$

2. Theverifier
accepts
Equal $(B(g_{1}), B(g_{2}), B(g_{3}))$ .

$T_{1}$$h$$W\in \mathcal{W}$as$U\in \mathcal{U}$ifier expect:
and:$\{-1,1\}$ to be the long codes corresponding
to the assignments to $W$ and $U$ respectively. Let $\pi=\pi^{W,U}$ themapping from $W$ to
2. Choose functions
independently.

$U$$\mathcal{F}_{\Lambda 4_{U}}\mapsto$$Pr[Acc]\leq E_{W}[1-\hat{B}_{\emptyset}^{2}]+O(\epsilon)$.

$f\in R\mu_{p}(\mathcal{M}_{U})$$Foreachy\{-ll\}as\in \mathcal{M}_{W}$

..

$A$

$\mathcal{F}_{\mathcal{M}_{W}}\mapsto\{-1,1\}$and

3.3.4 Test
Test

$g\in R\mu_{P}(\mathcal{M}_{W})$, choose a function

test
$h$

:

Not-All-$T_{3}$

1. According to the method of the verifier $V_{2PlR}$ , choose
random set
and its subset. The ver$B$

iff

Obviously, this test always accepts proper long code,thus
has peifect completeness. According to Fourier
analysis, acceptance probability for NO instance is denoted$T_{2}$..

p-\frac{1}{3}\end{array}$$T_{2}$

Test
is a slight modification of test
where the choiceof the function and the acceptance condition is different.
The procedure of the test is following.

3.

\frac{2}{3}-p(1, -1, -1), (-1,1, -1), (-1, -1,1)with each prob.

$T_{4}$$T_{4}$.

$T_{4}$is also a test for long code $B$ . The procedure of theis following.

1. The verifier chooses a random set. It expects$B$ :as a long code of an assignment
for $W$ . The verifier picks three functions:$M_{W}\mapsto\{-1,1\}$ as following.
$W\in \mathcal{W}$$\mathcal{M}_{W}\mapsto$$\mathcal{F}_{M_{W}}\mapsto\{-1,1\}$$g_{1},$ $g_{2},$ $g_{3}$$f(\pi(y))=1$ A $g(y)=1arrow h(y)=-1$$f(\pi(y))=1\wedge g(y)=-1arrow$$h(y)=\{\begin{array}{ll}1 with prob.

q/p-1 with prob.

$(g_{1}(y), g_{2}(y),g_{3}(y))$

1-q/p\end{array}$$=\{\begin{array}{ll}(-1, -1,1) with prob.

2p-1(-1,1,1), (1, -1,1) with each prob.

1 -- 432(-1,1, -1), (1, -1, -1) with each prob.

\not\in\end{array}$$f(\pi(y))=-1\wedge g(y)=1arrow h(y)=1$$f(\pi(y))=-1$ A $g(y)=-1arrow h(y)=-1$

2. The verifier accepts iff $(B(g_{1}), B(g_{2}), B(g_{3}))$

4. Accept iff $(A(f), B(g), B(h))\in S_{1}$ . Where$S_{2}=\{(1,1, -1),$ $(1, -1,1),$ $(1, -1, -1)$ ,$\neq$$(-1, -1, -1)$ .

$(-1,1,1),$ $(-1, -1, -1)\}$This test always accepts a proper long code, thus
has perfect completeness. Dividing acceptance condition insome cases and using Fourier analysis, the acceptance probaability of this test for NO instance can be bounded with the1following
expression.
$T_{4}$$]$

We can check that test
has perfect completeness inthe same way as . And the acceptance probability for NO
instance satisfies following expression.
$T_{2}$$T_{1}$$L|$$Pr[Acc]$$Pr[Acc]\leq E_{W}[1+\frac{\hat{B}_{\emptyset}-\hat{B}_{\emptyset}^{2}}{2}]+O(\epsilon)$.

$\leq E_{W,U}[\frac{5+\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}-2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}_{\emptyset}^{2}-3\hat{A}_{\emptyset}\hat{B}_{\emptyset}^{2}}{8}]+O(\epsilon)$,

3.4 The PCP Constmction
3.3.3 Test

$T_{3}$

Test
is a Not-All-Equal test of long code $B$ . While test
andchecks the consistency between tables $A$ and $B$ ,is a test for a single table $B$ . The procedure of the test
is following.
$T_{3}$$T_{1}$$T_{2}$$T_{3}$

We construct the PCP combining four tests described in
the previous section. Let
be a parameter detemiined
1later. The verifier performs each test with the following$t$$\eta\geq 0$

probability distribution.
$I$$T_{3}$

1. The verifier chooses a random set. It expects$B$ :as a long code of an assignment
for $W$ . The verifier picks three functions:$Pr[T_{1}]=Pr[T_{2}]=\frac{4\eta+4}{12+9\eta}$,$W\in \mathcal{W}$$\mathcal{F}_{\mathcal{M}_{W}}\mapsto\{-1,1\}$$g_{1},g_{2},$$g_{3}$$Pr[T_{3}]=\frac{\eta}{12+9\eta},$ $Pr[T_{4}]=\frac{4}{12+9\eta}$

(1)

134

$\eta_{2}$$\eta_{2}$$\eta_{1}$$\eta_{1}$Figure 1. Change in acceptance $prob\epsilon bIllty$
accordlng to executOonof the tests$prob\epsilon b\ovalbox{\tt\small REJECT} Ilty$

And thus the acceptance pmbability for NO instance is
$Pr[$

Accj

Flgure 2. Enlaged vtew around the minImum
value

4.1

Optimlzlng the Probabdity of the Tests

In Khot and Saket’s analysis, they detemine the proba$parameter\eta,althoughthedegreeofffeedomisboundedbybilityofselectingoneofthefourtestsbasedononlyone$$\leq E_{W,U}[\frac{4\eta+4}{12+9\eta}\frac{5-\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}+2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}_{\emptyset}^{2}+3\hat{A}_{\emptyset}\hat{B}_{\emptyset}^{2}}{8}$3 due to constraint $Pr[T_{1}]+Pr[T_{2}]+Pr[T_{3}]+Pr[T_{4}]=1$ ,or 2 if we force $Pr[T_{1}]=Pr[T_{2}]$ to eliminate
Funher$\hat{A}_{\emptyset}.$$+ \frac{4\eta+4}{12+9\eta}\frac{5+\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}-2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}_{\emptyset}^{2}-3\hat{A}_{\emptyset}\hat{B}_{\emptyset}^{2}}{8}$more, they did not explain why the probability of each test
is denoted as equation (1). So now we set the distribution as$+ \frac{\eta}{12+9\eta}(1-\hat{B}_{\emptyset}^{2})+\frac{4}{12+9\eta}(1+\frac{\hat{B}_{\emptyset}}{2}-\frac{\hat{B}_{\emptyset}^{2}}{2}I]+O(\epsilon)^{Pr[T_{1}]}=Pr[T_{2}]=q_{2}\underline{1},$$Pr[T_{3}]=1-\eta_{1}-\eta_{2},$ $Pr[T_{4}]=\eta_{2}$and calculate the acceptance probability for NO instance$\psi$.

$= \frac{6\eta+9+\eta^{2}-E_{W,U}[(\hat{B}_{\emptyset}+\eta)^{2}]}{12+9\eta}+O(\epsilon)$$Pr[Acc]$$\leq\frac{6\eta+9+\eta^{2}}{12+9\eta}+O(\epsilon)$.
$\leq E_{W,U}[\frac{\eta_{1}}{2}\frac{5-\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}+2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}_{\emptyset}^{2}+3\hat{A}_{\emptyset}\hat{B}_{\emptyset}^{2}}{8}$Above probability is minimized when
probability of each test becomes$\eta=\frac{1}{3}$. Now the$Pr[T_{1}]=Pr[T_{2}]=\frac{16}{45},$ $Pr[T_{3}]=\frac{1}{45},$ $Pr[T_{4}]=\frac{12}{45}$and finally the soundness $mms$ out to be$Pr$[Acc] $\leq\frac{20}{27}+O(\epsilon)\simeq 0.74074$ .

All the tests have perfect completeness and whole soundness is shown as above, that the proof of theorem 6 is completed.

4 Improving the Soundness$\eta_{1}5+\hat{A}_{\emptyset}-2\hat{B}_{\emptyset}-2\hat{A}_{\emptyset}\hat{B}_{\emptyset}+\hat{B}^{2}-3\hat{A}_{\emptyset}\hat{B}^{2}$$+ \overline{2}\frac{\emptyset\emptyset}{8}$$+(1- \eta_{1}-\eta_{2})(1-\hat{B}_{\emptyset}^{2})+\eta_{2}(1+\frac{\hat{B}_{\emptyset}}{2}-\frac{\hat{B}_{\emptyset}^{2}}{2})]+O(\epsilon)$$=1- \frac{1}{8}\frac{-28\eta_{1}^{2}-8\eta_{1}\eta_{2}-4\eta_{2}^{2}+24\eta_{1}}{8-9\eta_{1}-4\eta_{2}}$$- \frac{8-9\eta_{1}-4\eta_{2}}{8}E_{W,U}[(\hat{B}_{\emptyset}-\frac{2\eta_{2}-\eta_{1}}{8-9\eta_{1}-4\eta_{2}})^{2}]$$\leq 1-\frac{1}{8}\frac{-28\eta_{1}^{2}-8\eta_{1}\eta_{2}-4\eta_{2}^{2}+24\eta_{1}}{8-9\eta_{1}-4\eta_{2}}+O(\epsilon)$(3)Here, since the sum of the probability of selecting each test
is 1, and must satisfy the constraint$\eta_{1}$We can see that the analysis of section 3 is not tight.
In this section, we show that the soundness can be madesmaller under the same conditions. As a corollary, we havethe inapproximability results for a constraim satisfaction
problem where each constraint depends on at most threevariables (3-CSP).

(2)$+O(\epsilon)$$\eta_{2}$$L_{1}:\eta_{1}+\eta_{2}\leq 1$.

The third term in the equation (2) contains, whose value
may vaiy according to the input of the PCP. To bound theacceptance probability for every input, the term must have
non-positive value. It means that and must satisfy the$\hat{B}_{\emptyset}$$\eta_{1}$$\eta_{2}$135following constraint.

The point
is shown in the figure 2. Now the probabilitiesof these tests are$P_{2}$$L_{2}:8-9\eta_{1}-4\eta_{2}>0$

Because and represent probability, there are also constraints. We would like to find the valucs ofandwhich minimizes the acceptance probability underthese conditions.
The acceptance probability of the whole test is shown$\eta_{1}$$\eta_{1},$$Pr[T_{1}]=Pr[T_{2}]=\frac{24-\sqrt{6}}{60}\simeq 0.35918$,$\eta_{2}$$\eta_{2}\geq 0$$\eta_{1}$$Pr[T_{3}]=0,$ $Pr[T_{4}]=\frac{6+\sqrt{6}}{30}\simeq 0.28165$$\eta_{2}$vary satisfying
In the plot area, bold line
represents the border of the constraints
and , and thenumbers in the area represents the value of the level lines.
The figure shows that inside the area where the constraints
aoe satisfled, obviously there is no point where the acceptance probability $Pr[Acc]$ takes local minimum value, so$Pr[Acc]$ takes minimum on the boundary of constraint,
In the PCP construction of Khot and Saket, the probabilityof each test is defined as the pointin the figure 1, where$\eta_{1}$and$\eta_{2}$$\eta_{1},$$\eta_{2}\geq$$0,$ $\eta_{1}+\eta_{2}\leq 1,8-9\eta_{1}-4\eta_{2}>0$$L_{1}$$\frac{12}{45}I$

which implies that the test
is unnecessary. Finally, theacceptance probability of the PCP when an input 3-SAT-5
formula is NO instance, that is, the soundness becomes$T_{3}$$\psi$$L_{2}$$L_{1}$$P_{1}:( \eta_{1}, \eta_{2})=(\frac{32}{45},$

,

,

$Pr$

[Acc] $\leq\frac{16+\sqrt{6}}{25}+O(\epsilon)\simeq 0.73798\leq\frac{20}{27}\simeq 0.74074$ ,so we have succeeded to improve the result of Khot and
Saket. Now the theorem 6 is improved as the following.
Theorem 10.
$\forall\epsilon>0$

,

NP

$=$

naPCP $1^{1}s;\beta+e[O(\log n), 3]$

Furthermore, we simplified the PCP by showing thatthe test
is not necessary. We denote this PCP by$T_{3}$

shown in the flgure 2. The figure shows us that the acceptance probability at the point is clearly apart from minimum
value.
To obtain the minimum value of $Pr[Acc]$ on the boundary of the constraint , we set $\eta_{2}=1-\eta_{1}$ . Substimting$\eta_{2}=1-\eta_{1}$ in the equation (3), we have$L_{1}$$Pr[Acc]$$\leq 1-\frac{1}{8}\frac{-28\eta_{1}^{2}-8\eta_{1}(1-\eta_{1})-4(1-\eta_{1})^{2}+24\eta_{1}}{8-9\eta_{1}-4(1-\eta_{1})}+O(\epsilon)$$=1- \frac{1}{2}\frac{-6\eta_{1}^{2}+6\eta_{1}-1}{4-5\eta_{1}}+O(\epsilon)$.

Differentiating the above expression with respect toletting its derivative $=0$ , we have$\eta_{1}$

and

PCP

.

$\{T_{1},T_{2},T_{4}\}$4.2 Inapproximabmty of 3 CSP
Constraim Satisfaction Problem (CSP) is a problem toobtain a kind of object which satisfles the given constraints.
If the constraints are given by a form of Boolean functions
depending on the set of some variables, the object corresponds to an assignment to variables. Here, we discuss theinapproximability of CSPs where each constraint depends
on up to three Boolean variables. Such CSPs aoe called 3CSPs.
We assume that each constraint in CSPs has weight. The
weights are normalized so that their sum equals 1. Our objective in this 3-CSPs is to obtain an assignment that maximizes the total weights of satisfied constraints. A value ofthe 3-CSP instance , which is denoted as, is defined
as a maximum value of the total weights of satisfied constraints. The instance of $\omega(G)=c$ is called c-satisfiable
and l-satisfiable instances are simply called satisfiable.
We construct 3-CSP instances from our 3-bit PCP.
Each tests
andmakes randomly chosen threebit queries to the proof. We replace each query bit by a
Boolean variable and replace the acceptance condition by
a constraint. The weight of each constraint is the probability with which the triplet of queries is selected in eachtest. In this way, the tests are converted to 3-CSP instancesandrespectively, and we construct a new
3-CSP instanceby combining these 3-CSP instances. The weight of each constraint inis defined as the weight in its original instanceor
multiplied by the probability of the corresponding test in$G$$\frac{d}{d\eta_{1}}[1-\frac{1}{2}\frac{-6\eta_{1}^{2}+6\eta_{1}-1}{4-5\eta_{1}}+O(\epsilon)]=0$$- \frac{1}{2}\frac{30\eta_{1}^{2}-48\eta_{1}+19}{4-5\eta_{1}}=0$$30\eta_{1}^{2}-48\eta_{1}+19=0$

Solving the equation with respect to$\eta_{1}=\frac{24\pm\sqrt{6}}{30}$$\eta_{1}$.

, we have,$T_{1},$ $T_{2}$$G_{T_{1}},$$G_{T_{2}}$$\omega(G)$$T_{4}$$G_{T_{4}}$$G_{T_{1},T_{2},T_{4}}$$4\eta_{2}>0where\eta_{1},$$= \frac{24+\sqrt{6}}{d^{30}oub1}vio1atestheconstraintL_{2}.:8-9\eta_{1}-soesignisdete-inedby-Aboveca1-$

culation shows that the value of
andwhere $Pr[Acc]$
takes minimum in the area satisfying all constraints are$\eta_{1}$$\eta_{2}$$G_{T_{1},T_{2},T_{4}}$$G_{T_{1}},$ $G_{T_{2}}$$PCP_{\{T_{1},T_{2},T_{4}\}}$$G_{T_{4}}$.

In the above constructed 3-CSP instance
, the
value
is equal to the acceptance pmbability of$G_{T_{1},T_{2},T_{4}}$$P_{2}:( \eta_{1}, \eta_{2})=(\frac{24-\sqrt{6}}{30},$$\frac{6+\sqrt{6}}{30})$.

$\omega(G_{T_{1},T_{2},T_{4}})$

PCP$\{T_{1},T_{2},T_{4}\}$for the input 3-SAT-5 instance$\psi$. This is

136
obvious due to the conversion from PCP
to the 3CSP instance. Hence when is an YES instance,
the value ofcorresponds to the completeness, and whenof PCPis NO instance, the valueofcorresponds to the soundness. From thesefacts, we show the following inapproximability.
$\{T_{1},T_{2},T_{4}\}$$G_{T_{1},T_{2},T_{4}}$$\psi$$\omega(G_{7_{1},T_{2},T_{4}}\urcorner)$$\psi$$\{T_{1},T_{2},T_{4}\}$$\omega(G_{T_{1},T_{2},T_{4}})$, it is NP-hard to distinguish
Theorem 11. For any
between a satisfiable 3-CSP instance and asatisfiable 3-CSP instance.
$\epsilon>0$$( \frac{16\vdash\sqrt{6}}{25}+\epsilon)-$, the sum of the weights of satProof. In 3-CSP
isfied constraints equals to the acceptance probability of
PCP. Suppose that there is a polynomial time approximation algorithm which distinguish satisfiable 3-CSP
instance from-satisfiable 3-CSP instance. Thenthe algorithm can determine whether the acceptance probability of PCP
for some 3-SAT-5 instance is$G_{T_{1},T_{2},T_{4}}$$\{T_{1},T_{2},T_{4}\}$$( \frac{16+\sqrt{6}}{25}+\epsilon)$$\psi$$\{T_{1},T_{2},T_{4}\}$$thatthea1gorithmcandeterwhetherthe3- SAT- 5inhigherthanthesoundness\frac{16+\sqrt{6}}{\dot{m}ne25}+\epsilon ornot.T1\dot{u}simplies$

is satisfiable or not. Having such an algorithm,
we can solve an arbitrary NP decision problem by reducing
the problem to a 3-SAT-5 instance , that means the above
stance$\psi$$\psi$

mentioned task is NP-hard.

5Conclusion
In this paper, we improved the soundness of a non.

$Wehavealsoshownthatthenumkrothetestsintheadaptive3- bitPCPffomtheprevious\frac{20}{27,f}+\epsilon to\frac{16+\sqrt{6}}{used25}+\epsilon$

PCP can be decreased ffom 4 to 3. This results in a simplification of the PCP constmction. As a corollary, we showed
an improved inappmximability results of 3-CSPs.
On the algorithmic side, Zwick showed appmximation
ratio algorithm for any satisfiable 3-CSP instances. This algorithm was proved to be optimal by O’Donnel and Wu[11] under Khot’s d-to-l Conjecture. That is, they constructed a non-adaptive 3-bit PCP with soundness
and perfect completeness under the conjecture. However$d- t+1$ Conjecture still remains open (similar to the UniqueGames Conjecture), so obvious fumre work is decreasing
the soundness without such assumptions.
$\frac{5}{8}$$\frac{5}{8}+\epsilon$

References
S. Amra, C. Lund, R. Motwani, M. Sudan, and M. Szegedy.
Proof veriflcation and the hardness of approximation problems. Joumal of the ACM, $45(3):501-555$ , 1998.
[2] S. Arora and S. Safra. Probabilistic checking of proofs: A
new characterization of np. Joumal of the ACM, $45(1):7(L$122, 1998.
[3] M. Bellarc, O. Goldreich, and M. Sudan. Free bits, pcps andnonapproximability–towards tight results. SIAM Joumal ofComputing, 27(3):804-915, 1998.
[4] E. Friedgut. Boolean functions with Iow average sensitivity
depend on few coordinates. Combinatorica, $18(1):27-36$ ,
[1]

1998.

[5] V. Guruswami, D. Lewin, M. Sudan, and L. Tievisan.

A
tight characterization of np with 3 query pcps. In Proc. of

39th Annual IEEE Symposium on Foundations of Computer
Science, pages 8-17, 1998.
[6] J. HAstad. Some optimal inapproximability resuIts. Joumalof the ACM, $48(4);798-859,2\alpha)1$ .
[7] S. Khot. Hardness of coloring 3-colorable 3-uniform hypergraphs. In Proc. of the 43rd Annual IEEE Symposium on
Foundations of Computer Science, pages 23-32, 2002.
[8] S. Khot. On the power of unique 2-prover l-round games.
In Proc. of the 34th ACM Symposium on the Theory of Computing, pages 767-775, 2002.
[9] S. Khot. New techniques for probabilistically checkable
proofs and inapproximability results. In PhD thesis, Princeton University, Princeton, New Jersey, USA, 2003.
[10] S. Khot and R. Saket. A 3-query non-adaptive pcp with perfect completeness. In Proc. of the 2lstAnnual IEEE Conference on Computational Complexity, pages 159-169, 2006.
[11] R. O’Donnell and Y. Wu.
Conditional hardness
Submitted, Available atfor satisfiable 3-csps.
http: $//www$ .cs.cmu.edul $odonnell1papeis13bit$ -hardness.pdf.
[12] R. Raz. A parallel repetition theorem. SIAM JoumalofComputing, 27(3):763-803, 1998.
[13] U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three vaniables per constraint. In Proc. of the 9th Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 201-210, 1998.