Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

Подождите немного. Документ загружается.

5.3. Encodings 93

that v and w are close to Cn while V0 requires that both are indeed codewords.

Under the assumption that the coding scheme C is (r, q)-robust where log kn

is in

(9(r(n))

and logsn is in

(9(q(n))

we will now show that we can turn the

extended verifier Vo into an (r, q)-restricted extended verifier V1 which works for

all inputs. Note that we construct 1/1 just in order to show an application of

robust coding schemes and that in particular verifier 1/1 is not necessarily more

efficient than the extended verifier constructed in Example 5.9.

So let ~ < 1/8 be a positive rational which witnesses that the coding scheme C

is (r, q)-robust and let V~ and

be corresponding verifiers which witness that

C is (r, q)-checkable and (r, q)-correctable, respectively.

On an input (0 n,

vw)

the new verifier V1 first checks probabilistically whether v

and w are both ~-close to Cn by simulating V~ on inputs (0n,v) and (0n,w). In

case V~ rejects for at least one of these inputs, V1 rejects immediately. Otherwise

V1 starts simulating Vo on input (0 ~,

vw)

and random string T. While simulating

V0 for a single random string 7- the extended verifier 1/1 checks probabilistically

whether the constantly many symbols read by V0 while working on random

string T agree with the corresponding nearest codeword by simulating for each

such symbol the extended verifier Vb with an appropriate input. In case Vb rejects

during some of the latter simulations, then so does V1 for the random string ~- of

V0 under consideration, but otherwise 1/1 just simulates Vo and accepts or rejects

according to the latter simulation.

By construction 1/1 accepts an input

(O'~,vw)

in case v and w are identical

codewords in C,~. We show that 1/1 rejects such an input in case either, firstly,

the strings v or w are not t~-close to Cn or, secondly, both are ~-close to C,~

but the corresponding nearest codewords are different. In case v is not ~-close

to Cn then Va on input (O n, v) rejects for at least 3/4 of its random strings,

and then so does V~ due its simulation of V~. By symmetry the same holds for

w. So we can restrict the remainder of the verification to the case where both

strings are ~-close to Cn and we let y and z be the nearest codewords of v and

w, respectively.

Now consider the simulating computation on a single random string r of Vo. In

case all symbols read by V0 while working on this random string agree with y

and z, respectively, then V will behave like V0 would behave on input (O n,

yz).

On the other hand, in case some of the symbols read do not agree with y or z,

respectively, then the simulation of

results in rejecting with constant proba-

bility which can be chosen as close to 1 as desired, say with probability 9/10. But

we can assume that also Vo in case of rejection rejects its input for a fraction of

9/10 of all random strings, and consequently V1 rejects the input (0 n,

wv)

with

probability at least 81/100.

In the proof of Proposition 5.14 we apply robust coding schemes in essentially the

same way as in Example 5.12. The former application is however more involved

because the alleged codewords might belong to various codes in some given

94 Chapter 5. Proving the PCP-Theorem

coding scheme and might occur at arbitrary positions of the proofs 7to and 7h of

an extended verifier. Before we state the proposition we introduce some related

notation.

Definition

5.13. A pattern of length

c is a finite sequence

(nl,Q)...,

(no,it)

of pairs of natural numbers. We denote patterns by small Greek letters a, ~, ....

A pattern function

is a function from binary strings to patterns of some fixed

length c.

With the coding scheme C understood a binary string z

obeys a pattern a

equal to

(hi,

il) . . . , (no, ic) iff the string z contains non-overlapping codewords wt , . . . , wc

such that wj is in the nj-th code Cnj of C and starts at position ij of z. If we

require the wj only to be 5-close to Cnj instead of being elements of Cn~ the

string z is said to be

b-close to the pattern a.

For a string z which is 1~4-close to some pattern of length c the

nearest obey-

ing string

of z is the string obtained by replacing the subwords wl,..., wc of z

specified by the pattern with their respective nearest codewords.

An extended verifier V is

symbol constant

on 1to w.r.t, a pattern function x ~-~

a(x) in case for all

(x, (Tro,Th))

the extended verifier reads at most constantly

many symbols of the subwords of 7to which are specified by a(x) (Note that V

might read further symbols not belonging to these subwords.) Likewise, we define

the concept of an extended verifier being symbol constant on ft.

Observe that in Example 5.12 we have implicitly used a pattern function which

maps the string O n to the sequence (n, 1), (n, k, + 1) where kn is the codeword

length of the n-th code of the considered coding scheme.

While the formulation of Proposition 5.14 is rather technical, observe again that

its content is basically the same as in Example 5.12: given a resource bounded

extended verifier Vo where firstly, V0 works as intended for all inputs where

all designated alleged codewords are indeed codewords and secondly, for each

fixed random string, Vo reads only constantly many symbols of these alleged

codewords, then there is a suitably resource bounded extended verifier V1 which,

intuitively speaking, works for all inputs.

Proposition

5.14.

Let x ~-~ at(x), 1=0,1, be polynomial time computable pat-

tern functions, let C be a coding scheme and for all x, let kx be the maximal

codeword length of the codes specified by the first components of the pairs in

a0(x)

and

al(X)

w.r.t. C. Let Vo be an (r,q)-restricted extended verifier which is

symbol constant on 7to and on 7h w.r.t, ao and al, respectively. Let

0 :---- {(x,(rro,Th)) I rro

obeys ao andTrl obeys al},

and for all x let Az and Rx contain exactly the pairs in 0 which V accepts and

rejects, respectively.

5.3. Encodings 95

Assume further that the coding scheme C is (r', q')-robust and that there is some

constant c where for all x, we have r'(kx) <~ cr(Ixl) and q'(kx) <~ cq(Ixl ).

Then there is an (r, q)-restricted extended verifier V1 and a positive rational

b < 1/4 such that on the one hand V1 accepts all pairs in Az, and on the other

hand

Vx rejects all pairs (x, (~'o,Tq)) where 7to is not b-close to ao(X) or 7rl is not

b-close to ~l (X),

- V1 rejects all pairs (x,(Tro,Tq)) where 7to is b-close to so(x), 7rl is b-close to

(~1 (x), and where for the corresponding nearest obeying strings r' o and 7r' 1 the

pair (x, is in Rx.

In addition if the extended verifier Vo is constant then we can choose Vo to be

constant, too.

Proof. The extended verifier 1/1 essentially works like the verifier we have con-

structed in Example 5.12. Let the positive rational b witness that the coding

scheme C is (r', q')-robust.

While working on (x, (Tr0, rl)) where x has length n the extended verifier V1

first tests probabilistically whether 7to and 7rl are b-close to the pattern (~o(X)

and sl(x), respectively, and I/1 rejects immediately in case at least one of these

tests fails. In doing so we exploit that the coding scheme C is (r t, q')-checkable

in order to test for each of the constantly many pairs (nj,ij) specified by the

pattern So (x) whether proof 7r0 contains at position ij a string which is b-close

to the nj-th code of C, and likewise for sl and 7rl. Thus testing for closeness to

the patterns so(x) and (~l(X) uses at most O(r(n)) random bits and reads at

most O(q(n)) bits of the proof due to the assumption on r t and q'.

In case the test for closeness does not fail 1/1 proceeds by simulating V0, however

for each random string of Vo, the extended verifier V1 checks first whether the

constantly many symbols read by V0 from the segments specified by the patterns

s0 (x) and ~l(X) agree with the nearest obeying proof. By definition of nearest

obeying proof this amounts to check whether the constantly many symbols read

from the alleged codewords specified by the patterns a0(x) and Sl (x) agree with

the respective nearest codewords in the corresponding code. Again this test uses

at most O(r(n)) random bits and reads at most O(q(n)) bits of the proof due

to the fact that the coding scheme C is (r ~, q~)-correctable and by assumption on

r ~ and q~. The extended verifier V1 rejects in case this test fails for one of the

symbols and otherwise, it accepts or rejects according to the simulation of V0.

While verifying the behavior of 1/1 we proceed essentially as for the extended

verifier constructed in Example 5.12 and we leave the easy modifications to the

interested reader. Finally observe that by definition of robustness the subverifiers

used by 1/1 in order to test for 5-closeness and for agreement with the nearest

96 Chapter 5. Proving the PCP-Theorem

codeword are constant and that during the run of V1 for each random string of

Vo there are only constantly many invocations of these subverifiers. Thus in case

V0 is constant then so is 111. 9

The linear function and the polynomial coding scheme introduced next are both

based on functions over finite fields. For a prime p, we denote the field of p

elements by Fp. The elements of Fp can be identified with the natural numbers

0,... ,p- 1 in the natural way, and by this identification we extend the usual

ordering on the natural numbers to the field Fp.

5.3.3 The Linear Function Coding Scheme

We introduce a coding scheme based on linear functions over F2. Observe in

connection with Definition 5.15 that we identify the symbols 0 and 1 with the

zero and the unit of F2 and consequently the usual operations over F2 extend to

binary strings. Observe further that we identify a function from {0, 1} ~ to {0, 1}

with a binary string z of length 2 n where the i-th position of z corresponds to

the value of the function at the i-th string in {0, 1} n w.r.t, the lexicographical

ordering.

Definition 5.15. -

Given a

binary string

x = x 1

...

X n of length n, let lx denote

the function from {0, 1} '~ to {0, 1} defined by

ix(Y) = 2 xiYi.

i=1

For every natural number n, the linear function code (?lin is the set

v n

el_z" := {l,I x9

The linear function coding scheme C li" is given by the codes C n", cli",.., and

decoding functions" Ii, dec~i,, .. where" lin

aec o ,

(leClx I maps l~ to x.

We show first that the codewords in every linear function code C~ i" are indeed

at most 1/2-close.

Lemma 5.16. For every pair x and y of distinct binary strings of equal length,

the functions lx and ly agree on exactly 1/2 of the positions in their domain.

Proof. We let n be the length of x and y, and for ease of notation we assume

without loss of generality that x and y differ on their last bit. Further we note

that by symmetry it suffices to consider the case where the last bit of x is 0.

Thus for each binary string w of length n - 1, we have lx(wO) = lx(wl) and

5.3. Encodings 97

ly(wO) ~

lu(wl) and hence l~ and

agree on exactly one of the strings w0 and

wl, and disagree on the other. The assertion of the lemma then is immediate. 9

In order to prove that the linear code is checkable the following technical lemma

is required. This lemma intuitively states that whenever a function g is not close

to a linear function, this function g violates the linearity on a large fraction of

pairs of its arguments.

Lemma5.17.

Let J

< 1/3

be a constant and let ~ : ~ ~ F2 be a function

which is not J-close to a linear function. Then we have

Prob~,y[9(x) r 9(x + y) - 9(y)] > 2" (5.1)

Proof.

We show the lemma by contraposition: in case ~ does not satisfy in-

equality (5.1), then ~ is J-close to some linear function g. The function g will be

constructed as follows:

g(x)

:= majorityy{~(x + y) - ~(y)}, (5.2)

where majority denotes the value occurring most often over all choices of y;

breaking ties arbitrarily.

It remains to show that g and ~ are J-dose and that g is a linear function. We

first prove that g and ~ are J-close. By definition of g (cf. equation (5.2)), we

have for each x E ~2

Prob~[g(x ) = ~(x + y) - .~(y)] >/2" (5.3)

Starting with the negation of inequality (5.1) we obtain the following chain of

inequalities:

>/ Probz,y[O(x) r O(x + y) - O(y)]

>/ Prob~,u[O(x ) r

g(x) A g(x) = O(x + y) --

~(y)]

= Probx[~(x) r 9(x)]" Prob~,~[g(x) = ~(x + y) - ~(y) ] ~(x) # g(x)]

Since inequality (5.3) implies a lower bound of the second probability, we get:

>/ 2" Prob~[~(x) i~ g(x)].

Hence we obtain Probz[~(x) r g(x)] ~< J, i.e., g and ~ are &close.

To prove that g is a linear function, we first prove the following property of g:

Pa := Prob~[g(a) # .~(a + x) - ~(x)] ~ 5. (5.4)

98 Chapter 5. Proving the PCP-Theorem

By inequality (5.3) we know that pa <~ 1/2. Note that for some fixed a E F~2

each x + a E F~2 is equally likely if x E F~2 is chosen uniformly at random. Using

this fact and the negation of inequality (5.1), we obtain:

Prob~,y[.~(x + a) + ~(y) ~ ~(x) + ~(y + a)]

~< Probx,~[~(x + a) + ~(y) ~ ~(x + a + y)]

+ Probx,y[~(x) + ~(y + a) ~ ~(x + y + a)] ~< (f.

Starting with the last inequality, we obtain:

/> Prob~,y[~(x + a) - ~(x) ~ ~(y + a) - ~(y)]

= Z Probx,y[~(x + a) - ~(x) = z A ~(y + a) - ~(y) ~ z]

zEF2

= Z Prob~[~(x + a) - ~(x) = z]. Prob~[~(y + a) - ~(y) ~ z]

zEF2

Using the fact that F2 = {g(a), 1 - g(a)}

and the definition of pa in equation (5.4).

= (1-pa)p,+pa(1-p,)

Recall that

Pa <~

1/2, which implies 2(1 -

Pa) >1 1.

>/ pa

Now let a, b E F~2 be fixed. Using inequality (5.4), we derive:

Probz[g(a) +

g(b) ys g(a +

b)] = Probx[g(a) +

g(b) + [?(x) # g(a + b) +

~(x)]

< Probz[g(a) +

g(b) + ~(x) ~t ~(a + x) +

g(b)]

+ erob~[g(b) + ~(a + x) ~t ~(b + a + x)]

+ erobz[~(a

+ b + x) ~t g(a + b) +

~(x)]

-- 3.p~ ~< 3.& < 1.

Since the first term is independent of x, the probability must be either 0 or 1.

Hence, with probability 0 we get

g(a)+g(b) r g(a+b),

i.e., g is a linear function. 9

Now we are able to prove the checkability of linear function coding schemes. The

previous Lemma 5.17 suggests the following linearity test for the linear function

coding scheme.

LINEARITY TEST

Assume that input is O n .

Interpret 7r0 as ~

E C~ n.

Choose x, y E ~2 uniformly at random.

if (~(x + y) ~ ~(x) + ~(y))

then reject

else accept

5.3. Encodings 99

We simply check the linearity condition at randomly selected positions. When-

ever the considered function is not linear, we find with a positive probability a

pair of arguments on which the function will not behave as a linear function.

Of course this probability can easily be amplified by iterating the procedure

LINEARITY TEST.

Proposition 5.18.

The linear function coding scheme is

(n,

1)-checkable.

Proof.

Observe that the LINEARITY TEST will never reject a function ~ which is

indeed linear. Observe further that selecting the pair x and y at random requires

2n random bits and and that the LINEARITY TEST evaluates the function ~ only

at three positions. Thus in order to show that the linear function coding scheme

is (n, 1)-checkable, it suffices to show that for every positive rational ~ < 1/6

there is a constant k such that in case ~ is not b-close to some linear function,

then iterating the LINEARITY TEST k times results in rejecting with probability

at least 3/4. But this follows from the previous Lemma 5.17. 9

Proposition

5.19.

The linear function coding scheme is

(n,

1)-correctable.

Proof.

Let ~ be a function in ~2 which is 1/8-close to a linear function g.

Assume that we want to check whether ~ and g agree at some given position x.

Since ~ and g are 1/8-close, they disagree on at most 1/8 of all positions y, and

likewise, as y ~-~ x + y is a bijection on F~2 , ~(x + y) differs from

g(x + y)

for at

most 1/8 of all strings y. So we find that for at least 6/8 of all strings y we have

g(x) = g(x+y)-g(y) = 9(x+y)--~(y),

where the first equation follows by linearity of g and the latter by the preceding

discussion.

The desired test for agreement between ~ and g at position x now is straightfor-

ward: choose a random y and reject if 9(x) does not agree with 9(x + y) - 9(y).

Observe that this test will never reject a linear function g. Whenever this test

is applied to a function which is 1/8-close to a linear function g but does not

agree with g at position x then by the preceding discussion the test rejects with

probability at least 6/8.

Finally, we obtain a verifier V as required in the definition of (n, 1)-correctable

which works as follows: on input ((O n, x), 7r0), the verifier first runs LINEARITY

TEST and in case 7r0 does not represent some linear function in F~2 rejects imme-

diately with probability at least 3/4, and otherwise, it runs the test for agreement

at x described above. Observe that each of the two tests requires

O(n)

random

bits and evaluates 7r0 at (9(1) positions. 9

As a consequence of the previous propositions, we obtain the following corollary.

Corollary 5.20.

The linear function coding scheme is

(n,

1)-robust.

100 Chapter 5. Proving the PCP-Theorem

5.3.4 The Polynomial Coding Scheme

We introduce a coding scheme which is based on m-variate polynomials over Fp

where the parameters p and m depend on the length of the strings we want to

encode. Recall that an m-variate polynomial of degree d over Fp is a sum of terms

of the form axe1 ~ ... x~ k where a is in F v and where the maximum of il +... + ik

taken over all these terms is equal to d. Observe that such a polynomial defines

canonically a function from F~p to Fp.

We denote by <lex the strict lexicographic ordering on F~v which we obtain in the

usual way by extending the canonical ordering on Fp to sequences of m elements

of Fp. With the ordering <lex on l~p fixed, we can identify functions from F~n v to

Fp with strings of length p'~ over the alphabet Fp. More precisely, each such func-

tion g corresponds to the string g(xl)g(x2).., g(Xp,~) where xl <lexX2 .-. <lexXpm

are the elements of F~np.

Definition 5.21. Let p, m, and d be natural numbers where p is a prime and d

is less than p/2. Then we denote by C~, m, d) the code which contains exactly

the strings which correspond to m-variate polynomials over Fp of degree at most

Observe that the codewords in C(p, m, d) are strings over Fp of length pro. By

the theorem of Schwartz the assumption d < p/2 implies that distinct codewords

in a code C(p, m, d) are indeed not 1/2-close.

Theorem 5.22 (Schwartz). Two distinct m-variate polynomials of degree at

most d over some finite field F agree on at most a d/I N fraction of places in

their domain F r" .

Pro@ Given two different m-variate polynomials f and g over F of degree

at most d, their difference h is a m-variate polynomial that is not the zero

polynomial (i.e. the polynomial that has all coefficients equal to zero), since for

at least one tuple of exponents (il,..., ira) the coefficients of x~ 1 .-. x~ ~" in f and

i, in h is not zero. (Note that it

g disagree, and thus the coefficient of x] 1 -.-x m

is nevertheless very well possible that h(x) = 0 for all x E ~-~n, as the example

f(x) = x p and g(x) = x in the case F = F v and m = 1 shows. That example

does not contradict the theorem though, since we have d/IF I = p/p = 1 in this

case.) Thus it suffices to prove that any degree d polynomial f over F that is

not the zero polynomial takes the value zero at no more than a d/IF I fraction of

points of F ~ . We prove this by induction on m. The case m -: 1 is clear, since

a non-zero univariate polynomial of degree at most d has at most d roots.

So we assume m > 1 and note that ] can be written as

f(3:l,...,Xm)

= ~x~ . fi(x2,...,Xm)

i:-0

5.3. Encodings 101

where each fi is a (m - 1)-variate polynomial of degree at most d - i. Note that

since ] is not the zero polynomial, at least one of the ]i is non-zero. Let k be the

maximal index where this is the case. Thus we know by the inductive hypothesis

that for at least 1 - (d-k)/IF I of all values of (x2,... ,xm), f~(x2,... ,Xm) # O.

For any such value (a2,..., a,~), by choice of k the above representation yields

that ](xl, a:,..., a,~) is a non-zero univariate polynomial of degree at most k,

and thus is zero for at most k values of xl.

Therefore the fraction of non-zeroes of ] is at least

k d-k_ d-k k d

(1 - •)(1 IN

) 1> 1 IFI - 1 tFl'

which concludes the proof. 9

While defining decoding functions for the codes of the form C(p, m, d), first we

fix a strict ordering < on F~v. Then in order to decode a codeword q in C(p, m, d)

to a binary string u of length n, we consider the first n elements Xl < ... < xn

of F~p and interpret the value q(xi) as the j-th bit of u. Observe that by means

of the ordering < we are not only able to specify the places xj to be used in

the decoding, but we can also fix an ordering on the decoded bits. The latter

possibility will come in handy in connection with the splitting of codewords as

discussed in Section 5.5.1.

Definition

5.23. Let < be a strict

ordering

on a finite set D with IDI >1 2 and

let xl < ... < XlD I be the elements olD. For a function g from some superset of

D to a finite field F we let a(g, <) be the binary string Ul ... UlD I of length IDI

defined by

0 in case g(xj) is equal to the zero ofF (5.5)

uj = 1 otherwise

For a natural n <~ [D[ we let a(g, <,n) be the length n prefix of a(g, <).

Observe in connection with the definition of a(g, <) that the ordering < is total

and hence for each pair of different elements in its domain, the relation < either

contains (xi,xi) or contains (xj,xi). Thus in case the domain D of < contains

at least two elements then D is determined by <.

Now we can rephrase the remark preceding Definition 5.23: we will use decoding

functions of the form

dec: C(p,m,d) ~ {0,1} n (5.6)

q : ; a(q,<,n)

where < is a strict ordering on some appropriate subset of l~p.

However we have to take care that indeed for every binary string of the considered

length n there is an associated codeword. Remark 5.24 shows that this can be

102 Chapter 5. Proving the PCP-Theorem

achieved while working with polynomials of moderate degree in case we base the

decoding on the values of the codeword q on a set of the form H m where H is

a subset of Fp. In the setting of decoding functions of the form

a(q, <, n)

this

means that we specify a subset H of Fp with

IHml

/> n and a strict ordering <

H m

and then decode q to

a(q,

<,n).

Remark 5.24. Let H be a subset of Fp of cardinality h. Given some arbitrary

function g from H

to F, the polynomial

Z g(hl,...,hm)l-[ H x,-y (5.7)

hi - y

(hi .....

hm)eH 'n i-~l yeH-{hl)

has degree at most

m(h -

1) and agrees by construction with g on

H m.

Now

assume that we are given a strict ordering < on H~ n. Then for every binary

string x of length n less or equal to

IHI m,

there is an m-variate polynomial q

over Fp of degree at most

mh,

that is, a polynomial q in

C(p,m, mh),

such that

x is equal to

a(q,

<,n).

In case the parameters p, m and h are understood, we will denote a polynomial

of the form (5.7) as

low degree extension

of the function g.

In order to define the polynomial coding scheme, for each n, we choose parame-

ters ion, mn, dn which then specify a code

C p~ = C(p~, ran, d~).

In addition we

choose a subset H,~ of Fp~ and an appropriate strict ordering <n on H~ m- which

then yields a decoding function which maps a codeword q to the length n binary

string

a(q, <n, n).

More precisely we let for every natural number n >/16,

h,~ := [logn], mn := loglogn + 1; (5.8)

further we let

Pn be the smallest prime greater than 36 [log n] 2 (5.9)

(which is less than 72 [logn] 2 according to Bertrand's Postulate and which can

be found in time polynomial in n) and we let Hn contain exactly the first h,~

elements in Fn, w.r.t, the standard ordering on Fn. For n < 16, we choose the

parameters as in the case n -- 16.

We call a sequence <0, <x,...

admissible

iff firstly, for all n, the relation <a is

a strict ordering on H~" and secondly, in time polynomial in n we can go from

n and i to the i-th element of Hn m" and, conversely, from n and an element of

Hn m" to its index within H m. We fix an admissible sequence <o, <1,.... For the

moment, the orderings <n need not be specified to greater detail and in particular

up to Section 5.5.1 all results related to the polynomial coding scheme will not

depend on our choice of an admissible sequence. In Section 5.5.1 we will then add

further restrictions which are related to the checking of split representations.