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

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

5.4. Efficient Solution Verifiers 113

assignment of the given 3-CNF formula encoded by x, then the listing of the

values of all sums given in equation (5.15) is exactly the encoding using the

linear function coding scheme required by the definition of a solution verifier.

In what follows, the solution verifier will use the following two pattern functions

C~o(X) -- (n, 1) and C~l(X) = (n 2, 1)(n 3, n 2 + 1). As we have seen in Corollary 5.20

the linear function coding scheme C~ n is (m, 1)-robust. Thus, by Proposition 5.14

we can assume that the codewords in the proof specified by the pattern function

~0 and c~1 are indeed codewords of the linear function coding scheme, i.e., our

solution verifier assumes that for each input (x, (to,T rl)) the pattern function

ao(X) obeys ro and ~l(x) obeys ~rl. Moreover, Corollary 5.20 implies that a

(n 3,1)-restricted solution subverifier suffices for this test. For ease of notation

we denote by A, B, and C the codewords specified by the proof 7r = (Tro, 7h)

and the pattern functions a0 and al, i.e., 7r = (Tro,~rl) = (A, BC). Hence, the

solution verifier has to check that:

1. A, B, C are consistently defined w.r.t, the same vector a E ~,

2. vector a corresponds to a satisfying assignment.

In what follows we show how both conditions can be checked by a (n 3, 1)-

restricted solution verifier with linear function coding scheme. Clearly, for code-

words A, B, and C we have:

Vx, x' e~ : A(x).A(x')=B(xox') ~ b=aoa

and

Vx E ~ , y E ~2 A(x) . B(y) = C(x o y) r c = a o b.

Together with the above equalities, it is possible to check whether the three

linear function codes A, B, and C are consistently defined.

CONSISTENCY TEST

Interpret 7r ---- (ro,~1) as

(A, BC) as

discussed above.

Choose x, x' E ~ uniformly at random.

if (A(x) 9

A(x ~) ~

B(x o

x'))

then reject

Choose x E F~2 and y E F~2 2 uniformly at random.

(A(x). B(y) ~ C(x

o Y)) then reject

In CONSISTENCY

TEST a constant number of positions in the proof will be

queried and O(n 2) random bits are sufficient to determine the query positions.

Again in the procedure

CONSISTENCY

TEST a correct proof 7r will never be

rejected. On the other hand, an incorrect proof will be rejected with probability

of at least 1/4 as can be seen from the following lemma.

114 Chapter 5. Proving the PCP-Theorem

Lemma 5.38. If

there does not exist a vector a E F~2 such that A(x) = aTx,

B(y) = (a o a)Ty, and C(z) = (a o a o a)Tz, then

CONSISTENCY TEST

rejects

with probability at least

1/4.

Proof.

If b -- a o a and c = a o b, there is nothing to prove. Hence, we first

assume that b ~ a o a. Recall Lemma 5.37, i.e., for vectors a r & E F~2 we have

Prob~[aTx ~ &Tx] = ~.

(5.18)

This implies that matrices/3 r fl E F~22 satisfy

Prob~[flx ~ fix] t> ~. (5.19)

Combining these (in)equalities with the observation that

~T(a o a)~' = Z ~ ~' .a, .a~-~ = A(~)- A(~')

and

~Tbx' = ~ ~ ~,. b,,~. ~; = B(x o

~'),

we obtain under the assumption that b ~ a o a (note that a o a and b are

interpreted as matrices):

Probx,x,[A(x).

A(x') r B(x o

x')]

_~ Probz,~,[xT(a o a)x' ~ xTbx ']

= Prob~,~,[(a o

a)x' r bx' A xT((a o a)x') r xT(bx')]

= Prob~,[(a o

a)x' r bx']. Prob~,~,[xT((a o a)x') ~ xT(bx')i(a o a)x' ~ bx']

using equation (5.18) and (5.19)

/> ~.

Now we assume that c r a o b = a o a o a. Similarly, we obtain for tensors

Probye~2 bY r ~/Y]/> ~- (5.20)

With the following observation that

X T(aob)y' -~ EExi'ai'bJ,k'YJ,k = C(xoy)

i j,k

we obtain under the assumption that

c ~ aob

(note that

aob

and c are interpreted

as tensors):

5.4. Efficient Solution Verifiers 115

Prob~,u[A(x) 9

B(y) ~ C(x o

y)]

= Probx,y[xT(a o b)y ~ xTcy]

= Probx,y[(a o

b)y ~ cy A xT((a o b)y) #

xT(cy)]

= Proby[(a o

b)y ~

cy]-

Probx,u[xT((a o b)y) ~ xT(ey)[(a o b)y ~ cy]

using equation (5.18) and (5.20)

/> ~-

Now we have checked whether the codewords in the given proof r -- (~r0, rl) =

(A, BC)

are defined consistently w.r.t, some vector a E F~2. It remains to test

whether this vector a corresponds to a satisfying assignment of the given 3SAT

formula, i.e., whether

aTv ----

for some vector v. Due to equation (5.14) the

following procedure will suffice.

SATISFIABILITY TEST

Interpret x as an encoding of a 3-CNF formula ~.

Interpret ~r = (~ro, rl) as

(A, BC)

as discussed above.

Choose v E F~2 uniformly at random.

Compute c :=

c(v) E

F2 from ~ and v.

Compute $1 := S1 (v) e ~ from ~ and v.

Compute $2 := $2 (v) e I~22 from ~0 and v.

Compute $3 := S3(v) e F~2 s from ~ and v.

(c + A(S1) + B(S2) +

C($3) = 0)

then accept

else reject

Note that both algorithms will never reject a correct proof, while both algorithms

rejects a wrong proof with probability of at least 1/4. Repeating both test five

times, the rejection probability can be amplified to at least 3/4 as required in

the definition of a solution verifier. Altogether, we have proved the following

fundamental theorem.

Theorem 5.39.

There exists an

(n 3,

1)-restricted solution verifier with coding

scheme

C lin .

By definition of a solution verifier, we also have established the first step of

proving the PCP-Theorem as announced in Section 5.1.

Corollary 5.40. 3SAT E PCP(n 3, 1).

Since 3SAT is Alp-complete, each problem in Af:P can be reduced to 3SAT while

the size of the 3-CNF formula is polynomially related to the size of the original

instance. Thus, we obtain the following corollary.

Corollary 5.41. AlP C_ PCP(poly(n), 1).

116 Chapter 5. Proving the PCP-Theorem

5.4.4 A (log n, poly(log

n))-Restricted Solution Verifier

Theorem 5.42.

There is a

(log n,

poly(logn))-restricted solution verifier with

coding scheme

C p~

Proof.

Before giving the details of the solution verifier V satisfying the specified

resource bounds, we recall the exact format of the input given to V. This input

consists of the input string x encoding a 3-CNF formula ~o according to the

straightforward scheme given in Section 5.4.1 and the first part ~r0 of the proof

string that is supposed to encode a satisfying assignment of ~o according to

the polynomial coding scheme

C p~

Observe that since by Remark 5.32 an

assignment of ~o consists of the values of n propositional variables, where n is

the length of the input string

the proof string ~r0 is supposed to contain a

codeword of the code C p~ Recall from Definition 5.25 that these codewords

represent mn-variate polynomials of degree at most hn in each variable over the

field Fp., where

Pn, hn, and mn are

as defined in Section 5.3.4. Furthermore, if

denotes the set of the first hn elements of Fp., we can decode a code ~ for

an assignment g by noting that

g(i) = ~(x)

where x is the i-th element of H~"

according to the ordering <n on l~p" defined by the polynomial coding scheme.

By Proposition 5.14, using a pattern function c~0 that maps every string of length

n to the pattern (n, 1) and an empty pattern function al, it suffices to construct

a symbol constant (log n, poly(log n))-restricted extended verifier V, such that V

accepts all inputs (x, 7to) where 7r0 is a code for a satisfying assignment of the 3-

CNF formula ~o encoded by x, and V rejects all inputs (x, 7r0) where ~ro is a code

for an assignment that does not satisfy ~o. The assumptions of Proposition 5.14

are satisfied since the polynomial coding scheme is (log n, poly(logn))-robust

by Corollary 5.30, and furthermore the length of a codeword of C p~ is kn :--

pro. [logpn], and therefore log

is in

O(mn

logpn + loglogpn) = O(logn).

Thus we will assume from now on that ~r0 does indeed contain a code ~ for

some assignment g of ~o; the task of the verifier V consists therefore solely of

determining whether this assignment satisfies ~o or not. Note that according to

Remark 5.35 this is the case if and only if for all r = 1,..., 4 and 0 ~< i, j, k < n

we have

xr(i,j, k) . pr(g(i), g(j), g(k)) = O,

where the Pr are fixed polynomials that are linear in each variable and the Xr can

be computed from x in time polynomial in n. Since we have no immediate access

to g but only to its low degree extension ~, we also compute appropriate low

degree extensions Xr of the functions X~. Note that these can also be computed

in time polynomial in n, and that each )~ is a 3mn-variate polynomial over Fp.

of degree at most

in each variable. As a consequence, for r = 1,..., 4 the

functions

It(x, y, z) := )~(x, y, z). pr (0(x), O(y), 0(z))

are 3rnn-variate polynomials over Fp. of degree at most 2h,~ in each variable.

Observe that each single value of fr can be computed by our verifier using just

5.4. Efficient Solution Verifiers 117

three queries to the codeword ~. Furthermore, we know by construction that g

is a satisfying assignment if and only if for all r = 1,... ,4,

fr(x,y,z) = 0 for all x,y,z E H~ ~.

This means that the problem of verifying whether g is a satisfying assignment

is reduced to the task of checking whether the low degree polynomials fr are

identically zero on a certain part of their domain. At this point we will use

a test devised by Babai, Fortnow, Levin, and Szegedy to perform this check

probabilistically. That test is an extension of the so-called LFKN test used to

check whether the sum of the values of a polynomial over a certain part of its

domain is zero, which is due to Lund, Fortnow, Karloff, and Nisan. Both of

those tests will be described in detail in Section 5.6. Here we only state the

result about the procedure EXTENDED LFKN-TEST, which takes a function f

and an additional table T as inputs:

Theorem 5.56. Let m, d E N be constants and F be a finite field with IF[ >>.

4m(d+lHI) , where H C_ F denotes an arbitrary subset ofF. Let f: F "~ --+ F be a

polynomial of degree at most d in every variable. Then the procedure EXTENDED

LFKN-TEST has the following properties:

If f satisfies the equation

/(x) = 0 for all x E H m, (5.21)

then there exists a table TI such that EXTENDED LFKN-TEST(f, Tf ) always

accepts.

--Iff

does not satisfy equation (5.21), then EXTENDED LFKN-TEST(f,T) re-

jects with probability at least 1/2 for all tables T.

- EXTENDED LFKN-TEST queries f at one point, randomly chosen from F "~,

reads m entries of size O(m(d + IHI)log IFI) from T, and uses O(mlog IFI)

random bits.

Now we are able to construct a verifier V as desired: It simply uses four sec-

tions of its proof string ~h as tables needed by the EXTENDED LFKN-TEST for

checking whether the functions fr vanish on the subcube Hn 3rn" . The conditions

of Theorem 5.56 are satisfied: Since fr has degree at most 2hn in each variable,

we only need to ensure that Pn >/36mnhn. But this is the case by definition of

the parameters of the polynomial coding scheme. Thus we conclude that if 7r0

encodes indeed a satisfying assignment for x, there is a proof string 7rl such that

V accepts (x,(Tro,Th)), and if It0 encodes an assignment that does not satisfy

x, for any proof string lh the verifier rejects with probability at least 1/2. By

repeating the procedure twice, the rejection probability can be amplified to the

desired value 3/4.

118 Chapter 5. Proving the PCP-Theorem

What remains to be checked are the resource constraints: The verifier makes two

calls to EXTENDED LFKN-TEST,

each of them using O(3mn logpn) = O(logn)

random bits, and querying a single point of f~, which translates into three queries

of ~, and m,, entries of size O(9mnhn logpn) = O(poly(log n)) in its table, which

translates into queries of O(poly(log n)) many bits of 7h. Thus we conclude that

V is indeed a symbol constant (log n, poly(log n))-restricted extended verifier. 9

5.4.5 A Constant (log n, poly(log n))-Restricted

Solution Verifier

Note that the solution verifier given in Theorem 5.42 is not constant, since the

EXTENDED LFKN-TEST makes mn= [log n/log log n] + 1 queries to its addi-

tional table. As we will show in this section, that solution verifier can nevertheless

be turned into a constant verifier. To this purpose we use a technique similar to

one used in the proof of Proposition 5.29. Recall that the additional table used

there for showing the correctability of the polynomial coding scheme contained

polynomials Px,h that were supposed to describe the values of a low degree poly-

nomial g along the line {x + th I t 6 Fp }. We then argued that -- since Px,h

and g were both polynomials of low degree -- we could probabilistically check

whether such a polynomial P~,h described g correctly at all points of that line,

while actually querying g only at one single place during the test.

We now generalize this setting and consider not just lines, but general curves of

the form {uo + tul + t2u2 + ... + tCuc I t 9 Fp}, where uo,... ,uc 9 F~p are the

parameters of the curve, and c is called its degree. Note that in the case c = 1 the

notion of curve coincides with that of line. As in the case of lines, we consider

polynomials P~o ..... u~ Fp --~ Fp describing the values of g along the curve C with

parameters uo, 9 9

uc:

P~o ..... ~o(t) := g(C(t)), where C(t) := Uo + tul +... + tCuc.

Note that if the total degree of g is at most d, the degree of P~o ..... ~o is at

most cd. Thus, we will suppose that our table T contains for each (c + 1)-tuple

Uo,..., uc 9 F~np a univariate degree cd polynomial Puo ..... ~r represented by its

coefficients, that is supposed to be equal to P~o ..... ~,"

We further observe that, since each component of Uo + tul + ... + tCUc is a

polynomial in t of degree at most c, we can for each choice of c + 1 points

Xl,..., Xc+l find a uniquely defined curve C(xl,..., Xc+l) of degree c such that

C(Xl,...,x~+l)(i - 1) = xi for 1 ~< i ~< c + 1. We let P(xl,...,xc+l) de-

note the polynomial P~o ..... ~c where Uo,..., uc are the parameters of the curve

C(xl,..., xr Note that using e.g. Lagrange interpolation, those parameters

can be computed in polynomial time if the points xl,..., X~+l are given.

The interesting point is now that if we are sure that P := P(Xl,...,Xc+l)

correctly describes g along the curve C := C(xl,...,xc+l), we can infer all

values g(xl),..., g(x~+l) by simply evaluating P(O),..., P(c). Thus, all that we

5.4. Efficient Solution Verifiers 119

need are the coefficients of P, which we find by querying a

single

segment of

our additional table. But now we can use the usual argument: since P(-) and

g(C(.)) are

both polynomials of degree at most cd, they are either equal or agree

at most at

cd/p

places. Thus we will be able to ensure probabilistically that P

does indeed describe g along C correctly by simply verifying

P(t) = g(C(t))

for

a single point t E Fp, chosen uniformly at random. The details of this argument

will be given below.

Theorem

5.43.

There is a constant

(log n,

poly(logn) )-restricted solution ver-

ifier with coding scheme

C p~

Pro@

We denote the solution verifier from Theorem 5.42 by Vo. Our goal is

now to turn that verifier into a constant verifier. Since Vo queries only constantly

many segments of 7r0, we have to take care only of the queries to rrl. We alter Vo

into a solution verifier which works within the same resource bounds but expects

the part 7rl of its proof to be suitably encoded. By using the technique discussed

above, the new verifier will query only constantly many symbols of this codeword

plus constantly many segments of length poly(log n) in an additional part of the

proof.

Before describing the operation of the new verifier in detail, we note that al-

though the length of the proof string 7rl is not determined a priori, for any given

input x of length n, the total number of places of 7rl the verifier Vo could access

for

any

random string v is at most 2 ~176 - O(poly(log n)) -- O(poly(n)). Thus,

we can modify V0 so that, given an input x, it first constructs in polynomial

time a list of all places i of 7rl that might be accessed (by simply enumerating

all possible random strings), sorts them into a list i0, Q,... in ascending order,

and proceeds then with its normal operation while replacing any lookup of 7rl

at place ij with a lookup of 7rl at place j. This verifier V~ is obviously also a

solution verifier, and satisfies the same resource constraints as Vo.

Therefore, we can assume without loss of generality that V0 expects a proof 7rl

of length

l(n)

where

l(n)

is in O(poly(n)) when given an input x of length n.

Furthermore we denote by

q(n)

the number of queries to 7rl made by Vo. (Note

that by adding dummy queries we can always assure that V0 makes the same

number

q := q(n)

of queries to rrl for any input of length n and any random

string.) Since

q(n)

is in O(poIy(Iogn)), there are constants e and N such that

for all n/> N we have

q(n) <~

[logn] e. We assume from now on that the new

verifier will be called only with inputs of size n/> N, since for n < N we can

simply consider the old verifier V0 as constant verifier. The new verifier that

we are going to construct will then expect its proof to contain a code g for

g~poly

Zrl according to the code

Ve_t_2,1(n) ,

and in addition a table T containing the

polynomials Pu0 ..... ~q-1 supposed to describe the values of g along all curves

with parameters

uo, . . . , uq-1 E ~ ,

where

:= Pe+2,1(n)

and m

:----

ml(n)

are the

defining parameters of the code

CPe+~t(n)

and

q := q(n).

Note that by definition

of the polynomial coding scheme with parameter e + 2, the field size p will be

120 Chapter 5. Proving the PCP-Theorem

at least 36

[logl(n)] e+2.

Since the degree d := dl(n) of g satisfies d <~ [log/(n)] 2

according to that definition, and furthermore

q(n) <<.

[log n]e ~ [log/(n)] e holds

by definition of e, this implies

p >. 36qd.

By Proposition 5.14, using an empty pattern function a0 and a pattern function

am that maps every string of length n to the pattern

(l(n),

1), it suffices to con-

struct a symbol constant (log n, poly(logn))-restricted extended verifier V such

that for all x and g where g is a code for a proof string rl such that V0 accepts

(x, (Tr0,7h)), there is a table T such that V accepts (x, (Tr0, g, T)), and that for all

x and g where g is a code for a proof string ~h such that V0 rejects (x, (Tro, ~h)),

V rejects

(x,(lro,g,T))

for any table T. The assumptions of Proposition 5.14

are satisfied since the polynomial coding scheme is (log n, poly(log n))-robust by

Corollary 5.30, and furthermore the length k~(n) of a code for a string of length

l(n)

satisfies log kz(n) = O(log

l(n)) =

O(log n).

The verifier V proceeds now as follows: It simulates the operation of V0 on the

given input x and random string r to compute the places al,...,

of 7rl that

V0 would query, and the corresponding values xl,..., Xq E ~ where each x~ is

the ai-th element of ~ according to the ordering <n defined by the polynomial

coding scheme. (Recall that the decoding function was defined so that to get

the ai-th bit of the string encoded by the codeword g, we have to check whether

the value

g(xi)

equals zero or not, where g is interpreted as function l~p --~ Fp.)

The verifier further computes the parameters of the curve

C := C(xl,... ,Xq),

and looks up the polynomial

P := P(xl,..., xq)

from its additional table T. It

then chooses t 9 Fp uniformly at random and checks whether P(t) = g(C(t)),

rejecting if this test fails. It finally sets vi = 0 if

P(i)

= 0 and vi = 1 if

P(i) ~ 0

for 1 ~ i ~< q and continues simulating what V0 would do, if its queries of 7h at

places

al,..., aq

had resulted in

vl,..., Vq,

respectively.

This verifier V has indeed the required properties: Suppose first that g is indeed

code for a proof string 7h such that V0 accepts (x, (Tro, 7rl)). If we then construct

a table Tg by correctly tabulating all curve polynomials of g, the verifier V will

correctly retrieve all values vi, and thus accept as well. Now suppose on the

other hand g is a code for a proof string ~rx such that Vo rejects (x, (Tr0,Trl)).

This means that Vo rejects (x, (Tr0,Th)) on at least 3/4 of all random strings,

and thus V rejects

(x,(Tro,g,T))

on at least 3/4 of all random strings where

the polynomial P describes the values of 9 along the line C correctly, and thus

the values vi are retrieved correctly. Furthermore, since P(.) and

g(C(.))

are

univariate polynomials of degree at most (q - 1)d, in all cases where P(-)

g(C(.)) they can agree at most at (q - 1)d points t 9 Fp, and it follows that

(q - 1)d 1

Probt[P(t) = g(e(t))] <<. p <~ ~,

where the second inequality holds since

p >1 36qd as

remarked above. But this

means that on at least 3/4 of all random strings where P does

not

describe g

along C correctly, the verifier V rejects as well. Since we have shown that V

rejects in at least 3/4 of all cases where P(-) _=

g(C(.)),

and it also rejects in

5.5. Composing Verifiers and the PCP-Theorem 121

at least 3/4 of all cases where P(.) ~ g(C(.)), we can conclude that the totM

rejection probability of V is at least 3/4. Finally, we note that in addition to

the random bits used by V0, we only need O(Iogp) = O(log log n) random bits

to choose t, and that V queries its proof string -- apart from the queries of 7r0

done by V0 -- only at a constant number of symbols of g and a constant number

of segments from T, each of size O(qd log p) = O(poly (log n)). 9

5.5 Composing Verifiers and the PCP-Theorem

5.5.1 Splittable Coding Schemes

The proof of the PCP-Theorem works by composing the extended verifiers we

have seen so far. In connection with the composition of extended verifiers we

encounter a technical problem: assuming that a proof is partitioned into non-

overlapping blocks of length l, for some fixed k and for every selection of k

such blocks, we want to test efficiently whether some designated string of length

n -- kl is equal to the concatenation of the k blocks selected. As usual we obtain

an efficient probabilistic test as desired by working with codes instead of the

strings themselves: we fix some appropriate coding scheme with codes Co, C1 ...

and we assume that firstly, instead of the designated string we are given a code

for it in C~ and secondly, in case a block holds a binary string x then this block

is given as a code z in Cn such that z decodes to a string which has x as a prefix.

Definition 5.44. For a string w and natural numbers i <~ j ~ [w I we denote by

w[i:j] the substring of w which corresponds to the places i through j.

With a code C and a decoding function dec understood, we say the sequence

zx,. . . , z~ of codewords in C is a split representation of a codeword zo in C iff

for some l, the string dec(zo) is equal to dec(zl)tl:l]dec(zz)[l:t].., dec(zk)[l:l].

The coding scheme C = (C1, deCl), (C2, dec2),.., is (r, q)-splittable into k parts

iff there is an (r, q)-restricted extended verifier V where for every natural number

l and for n -- kl there is a subset L, of C~ such that

1. /or each string x of length I there is a codeword w in Ln where x is equal to

deca(w)[x:t],

2. for all zl,...,Zk in Ln there is some zo in Cn such that firstly, V accepts

the input (On,zo...zk) and secondly, zl,... ,Zk iS a split representation of

the codeword Zo,

3. V rejects all inputs (O n, zo... zk) where the strings Zo,..., Zk are all in Cn,

but zl,..., zk is not a split representation o] zo,

122 Chapter 5. Proving the PCP-Theorem

4. for each input (0n,Tr0) and random string T the extended verifier V reads at

most constantly many symbols from 7to where 7to is considered as a string

over the alphabet En of the code Cn.

A coding scheme C is (r, q)-splittable iff for every natural number k >/ 1, the

coding scheme is (r, q)-splittable into k parts.

With the notation introduced in Definition 5.44 at hand we now reconsider the

problem to check whether the concatenation of k binary strings xl,..., Xk is

equal to some designated string Xo. Given an (r, q)-splittable coding scheme C

with codes C1, C2,... and an extended verifier V and subsets Ln of Cn as in

Definition 5.44, we are able to construct a corresponding probabilistic test.

We assume that the blocks have length ! and we let n = kl. The test will receive

as input appropriate encodings ZO,...,Zk of the strings XO,...,Xk. In case a

block holds a binary string x, we assume that the block is given as a code z in

Ln according to Condition 1 in Definition 5.44, that is, as a code z which decodes

to a string of the form xy. Further we assume that in case the string Xo is in

fact equal to the concatenation of Xl through xk, then xo is given as a code Zo

for x0 in Cn according to Condition 2, that is, as a code Zo which in particular

possesses the split representation Zl,..., Zk. We now obtain a probabilistic test

as desired by running the extended verifier V on input (O n, zo... Zk). In case the

designated string is in fact equal to the concatenation of Xl through xk then

the input is accepted by our choice of the zj . On the other hand, according to

Condition 3 the extended verifier V will not accept the input in case the zi are

all in Co but Zl through zk are not a split representation of Zo.

By the preceding discussion an (r, q)-restricted extended verifier can use a sub-

verifier in order to check probabilistically whether, intuitively speaking, k codes

from Cn which figure at arbitrary places in the proof contain the same infor-

mation as some code from Cn which occurs somewhere else as a segment of the

proof. Remark 5.45 shows that for an (r, q)-robust coding scheme C this subver-

ifier can in fact be chosen to work as intended for all possible inputs and not

just for inputs which obey the pattern function which is implicit in our notation

(0% z0... zk).

Remark 5.45. The concept of a coding scheme which is (r, q)-splittable is de-

signed to be used with coding schemes which are in addition (r, q)-robust. Given

such a coding scheme and an extended verifier V as in Definition 5.44, then

according to Proposition 5.14 for some positive rational 6 there is an (r,q)-

restricted extended verifier V0 which basically works as V, but which in addition

can be shown to reject every input (On,yo... Yk) for which either some of the

strings Yi is not 6-close to Cn or the strings Yi are all 6-close to codewords z~ in

Cn but the strings zl,..., Zk are not a split representation of z0.

Proposition

5.46. The linear function coding scheme is (n, 1)-splittable.