Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

• • •

Definition 4.5.2. For vectors X E z� and E Z'!J' ' let X 0 denote the outer product z E z�m ' given by Zij = Xi * Yj . Note that although z is an l X m matrix, we will sometimes view it as an 1m-dimensional vector. The exact view should be clear from the context.

y

y

4.5 A long and robust proof system

55 2

Let b = a o a and let c = a o b. Further let A : Z� --+ Z2 , B : Z� --+ Z2 3 and c : Z� --+ z2 be the linear functions whose coefficients are given by a, b and c. n A( x )

L

=

i= l

n

B(y)

=

=

n

L L b;; * Yij i=l j =1

n

C(z)

a; * x;

n

n

L L L Cij k * Zij k

i= l j = l k = l

The encoding scheme for a that we choose is the following: The prover writes down the values of the functions A, B and C explicitly for each input. The intuition for choosing this encoding is the following:

1 . By using the results on linearity testing it should be possible to verify the authenticity of such codewords. 2. Given the information specified above correctly, one can compute the value of any degree 3 polynomial in n variables at the point a. 3. A 3-CNF formula should be closely related to degree 3 polynomials. We now provide precise statements of the claims above and prove them. Lemma 4.5.3. Given functions A, B and C, and a constant b exists a tester T, and a constant c such that:

>

0 there

- If there exists a vector a such that A, B and C give the encoding of a, then T ( r , A, B, C) outputs PASS for all r E {0 , 1 } 0 ( n 3 ) . - If for all vectors a, at least one of the distances d(A, A) , d(B, B) and d(C, C) is not bounded by b, then T(r, A, B, C) outputs FAIL, for at least half the random strings r E {0, 1} O ( n 3) . Furthermore, for any fixed choice of r, T 's output depends on at most c values of A, B and C. Proof: The tester T first tests that the functions A, B, C are linear functions, using the tester from Lemma 4.5 . 1 . This yields strings a , b and c such that: if A,B and C are the linear function with coefficients a, b and c respectively, then d(A < A)i, d(B, B) and d(C, C) are all bounded by b . This tester needs to probe A, B and C in 0(( j ) 2 ) places. Further note that at this point we could use the self-corrector of Lemma 4.5.2 we can compute the functions A, B and C at any point correctly with high probability. At this point the only aspect left to be tested is that b = a o a and that c = a o b. We now test that these properties hold. These tests will be based on the randomized algorithm for verifying matrix products, due to Freivalds [56] . Consider the n x n matrix X such X;j = b;j and let Y be the n x n

56

4. Transparent proofs and the class PCP

matrix obtained by viewing a o a as an n x n matrix. The property we wish to verify is that X = Y. The idea of Freivalds' matrix multiplication checker is to consider a random vector a: E Z2 and verifying that a:T X = :z: T y . It can be shown that if X :j: Y then this products differ with probability at least half. Further, consider a randomly chosen vector y E 22 and the products :z:T Xy and zTYy. If a:T X =/: :z:Ty then these products differ with probability half. Thus with probability at least a quarter, we have that :z:T X y :j: :z:Ty y, if X =/: Y. But now consider the product xTXy: this is equal to B(x o y) , and the product xT(a o a)y equals A(x) * A(y). Thus the identity can be tested by evaluating the functions A and B at three points in all. The process can be repeated constantly many times to get high enough confidence. A similar test checking that C ( x o y) = A(x) * B(y) concludes the test. 0 Next consider the task of evaluating any degree 3 polynomial f at the point a11 . . . , an. f can be written as f(a l , . . . , an )

=

a+

L ai + L

• e s,

(i ,j )es,

L a; + L

ai * ai +

L

(i,j , k)es,

a; * ai * ak

L

Cij k b;j + ( i ,j)ESo ( i ,j,k)ESa a + A( X (Sl )) + B ( X (S2 ) ) + C ( X (S3 ) )

a+

i E S,

(where S1 1 S2 and S3 are sets that depend only of f and X (SI ) , X (S2) and X(S3 ) are the characteristic vectors of these sets). Thus any degree 3 polyno­ mial can be evaluated at a by computing A. B and C at one point each. Next we show that 3-CNF formulae are closely related to degree 3 polynomials.

Lemma 4.5.4. Given a 3- CNF formula , and an assignment a1, . . . , an , a degree 3 polynomial J> : 22 --+ zt can be constructed (without knowledge of

the assignment} such that

- If all · · · • an satisfies , then ;fi(a1 , . . . , an ) = 0 . - If a1, . . . , an does not satisfy then ;fi(a1, . . . , an ) = 1 with probability 1/2 .

Proof: We first arithmetize every clause Cj into an arithmetic expression C; over Z2 (over the same set of variables) , so that Cj is satisfied by a if and only if C; evaluates to zero. This is done as follows: If Ci is the clause v 1 V v2 V •V3 then Cj will be the expression ( 1 - vi ) * ( 1 - v2 ) * v3. Notice that each clause gets converted in this fashion to a degree 3 polynomial and the whole formula is satisfied only if each expression Cj evaluates to zero at v; = a; . Now consider taking the inner product of the vector < cl . . . . ' Cm > with a randomly chosen m-bit vector r. u the vector < C1 1 , em > is not identically zero then the inner product will be non-zero with probability half. Thus if we let J> be the inner product i.e. , I:j= 1 r; * Cj then J> is a degree • • •

4.6 Small proofs with constant query complexity: recursion

57

three polynomial in the n variables which satisfies the conditions required by the Lemma. 0 Thus we are in a position to prove the following lemma. Lemma 4.5.5. NP � PCP(poly(n), 1 ) . Proof: For any language L and fixed input length n, we create a 3-CNF for­ mula

w E L We then expect the prover to encode the string a = w · y using the encoding mechanism (i.e., the functions A, B and C) as constructed in this section. The tester T first verifies that the encoding describes a valid assignment, using Lemma 4.5.3 and then verifies that it corresponds to a satisfying assignment of

Lemma 4.5.6. NP C rPCP(poly(n), 0( 1 ) ) Proof: To convert the proof system of Lemma 4.5.5 to a rPCP (poly( n ) , 0( 1 ) ) proof system we observe that if the input w = w 1 · w 2 · · · We are each encoded by the parities of all their subsets, then the last phase of the tester's verifi­ cation process, j ust compares entries from the encodings of w1 etc. with the value of A at some point. Thus there exists an encoding scheme E and a proof 1r such that the tester looks at 0 ( 1 ) bits from the encodings of w 1 , · · · , W e and 0 ( 1 ) bits of the proof 1r and verifies that w1 · w2 · · · We E L. 0 4 . 6 Small pro ofs with constant query complexity: recursiOn

The results of the previous two sections can be combined using the recursion lemma, Lemma 4 . 3 . 1 to get proofs which combine the best of both the proof systems. Theorem 4.6.1. NP C rPCP(Iog n , O ( l ) )

58

4. Transparent proofs and the class PCP

Proof: Using Lemmas 4.3.1 and 4.4. 1 , we get that NP C rPCP(log n, polyloglogn). Now using this result and Lemma 4.5.6, we see that NP C rPCP(log n, 0 ( 1 ) ) .

0

The result can be extended to get the following theorem for general NTIME classes.

Theorem 4.6.2. If L

E

NTIME(t(n) ) , then L

E

PCP(log(t(n) + n), 0 ( 1 ) ) .

Thus the following corollaries become immediate. Corollary 4.6.1. NE = PCP(n, 0 ( 1 ) ) Corollary 4.6.2. NEXPTIME = PCP(poly(n), 0 ( 1 ) )

4 . 7 D iscussion

Most of the work prior to 1992 [20, 19, 50] were essentially focussed on de­ riving PCP containments for nondeterministic time bounded classes. While these results lie at the core of the constructions described in this chapter, none of them translate directly into any rPCP results. The only work prior to 1992, which can be described in terms of rPCP systems are the results on "constant-prover proof systems" (i.e., multiple prover proof systems which allow only one round of interaction with upto a constant number of provers) [29, 53, 37, 85, 48] . In particular the results of Lapidot and Shamir [85] and Feige and Lovasz [48] can be scaled down to get rPCP (polylog n, polylog n) protocols for NP. The rPCP(log n, polylog n) protocol given here is somewhat inspired by the works of Lapidot and Shamir [85] and Feige and Lovasz [48] on parallelizing the MIP = NEXPTIME protocol, and in particular shares similar goals, but the protocol and proof are new to Arora, Lund, Motwani, Sudan and Szegedy [8] . In particular, the amount of randomness used in the protocols of [85, 48] seems to be superlogarithmic and [8] are able to reduce this to O(log n). Moreover, their final protocols does not seem to be able to handle the situation where the input comes in a constant number of error­ corrected pieces. The rPCP(poly(n), 0 ( 1 ) ) protocol discussed in this chapter is new to Arora, Lund, Motwani, Sudan and Szegedy [8] . The recursive proof construction technique described here is almost entirely due to the work of Arora and Safra [6] , modulo the formalism which may be different here.

Open Questions. The most important question that does remain open is what is the smallest number of bits that need to be read from a transparent proof to achieve a fixed probability of detecting a false proof. In the next chapter a connection is pointed out between the PCP proof systems and 3SAT. This connection shows that if the probability of detecting cheating is allowed to

4. 7 Discussion

59

be an arbitrarily small constant, then reading 3 bits of the proof suffices. Moreover, if the error of the verifier is expected to be one sided, then 3 bits are necessary ( the computation of a verifier when it reads only 2 bits can be equated to the satisfiability of a 2-SAT formula) . Lastly, in this regard, it may be pointed out that if the error of the verifier is allowed to be two-sided then even reading two bits suffices. Our result shows that any proof can be converted into a transparent proof which is within a polynomial factor of the size of the original proof. In contrast to this, the transparent proofs of Babai, Fortnow, Levin and Szegedy [19] are nearly linear in the size of the original proof. This raises the question of whether the proofs of this section can be compressed into a nearly linear size. This question seems to get mapped down to the question of the efficiency of the low-degree test and the question about the field sizes required for the Arora-Safra Tester that is raised at the end of Chapter 3.

A ddendum. In the last few years the PCP technology has seen enormous amounts of progress - we attempt to summarize this briefly here. Bellare, Goldwasser, Lund and Russell [28] initiated the attempt to reducing the con­ stants in the proof systems described here. They show that the query com­ plexity of a proof system can be made as small as 30 bits while guaranteeing that incorrect proofs will be rejected with probability half. This number was further reduced by Feige and Kilian (47] and by Bellare, Goldreich and Sudan [27] who report that 16 bits suffice. Much of this improvement comes about due to an improvement in the parameters associated with a constant prover proof system for NP [28, 47, 108, 98] . A second factor in the improvements has been improvements in analysis of the "linearity test" - which also has some fairly tight analysis now due to [28, 26] . A different objective has been the blowup in the size of a transparent proof as compared with the original proof. This was the original objective of Babai, Fortnow, Levin and Szegedy [19] who set the goal of getting a transparent proof with a blowup of only O(n1+'). This goal was met by Polishchuk and Spielman [97] who give a proof system with con s tant query complexity and O(n 1 + • ) size proofs. A third di­ rection of research combines the two objectives above trying to combine the goal of small proof sizes with small ( explicit) query complexity. Friedl and Sudan [55] report proofs with such explicit parameters, giving proofs with O(n2+•) size with a query complexity of 1 65 bits.

5 . Hardness of approximations

The notion of NP-completeness ( Cook [41] , Levin [86] and Karp [80] ) was developed primarily as an attempt to explain the apparent intractability of a large family of combinatorial optimization problems. The resulting theoret­ ical framework (cf. [60] ) was defined mainly in terms of decision problems obtained by imposing bounds on the value of the objective function. This permitted the development of an elegant body of results and the formal­ ism sufficed for the purposes of classifying the complexity of finding optimal solutions to a wide variety of optimization problems. Attempts to extend this analysis to the task of finding approximate so­ lutions to the same set of problems, was not very successful. Problem which seemed equivalent when the goal was to find exact solutions, seems to break apart into problems of widely varying complexity when the goal was relaxed to that of finding approximate solutions. Some problems like the knapsack problem have extremely good approximation algorithms [59] . Other problems have algorithms where the error of approximation can be made arbitrarily small, but the penalties paid for improved solutions are heavy. An example of such a problem is the task of minimizing the makes pan on a parallel machine ­ a scheduling problem studied by Hochbaum and Shmoys [73] . Yet other prob­ lems like the Euclidean TSP and vertex cover seemed approximable to some constant factor but not arbitrarily small ones; and finally we have problems which seem no easier to approximate than to solve exactly e.g. Chromatic number. Some initial success was obtained in showing the hardness of even ap­ proximating certain problems: For the traveling salesman problem without triangle inequality Sahni and Gonzalez [1 03] showed that finding a solution within any constant factor of optimal is also NP-hard. Garey and Johnson [58] showed that the chromatic number a graph could not be approximated to within a factor of 2 - f. They also show that if the clique number of a graph cannot be approximated to within some constant factor, then it cannot be approximated to within any constant factor. Hochbaum and Shmoys [71, 72] study some min-max problems where they show tight bounds on the factor to which these problems may be approximated unless NP = P . The lack o f approximation preserving reductions among optimization problems seemed to isolate these efforts and the search for such reductions

62

5 . Hardness of approximations

became the goal of a wide body of research [10, 1 1 , 12, 95] . The most success­ ful of these efforts seems to be the work of Papadimitriou and Yannakakis [93] where they used a syntactic characterization of NP due to Fagin (45] to define a class called MAX SNP. They also defined a particular approximation preserving reduction called the L-reduction ( for linear reductions ) used these reductions to find complete problems for this class. All problems in this class were approximable to some degree, and the complete problems for the class seemed hard to approximate to arbitrarily small factors. The class MAX SNP seemed to provide a much need framework to deal with approximation prob­ lems and this was evidenced by the large number of problems which were subsequently shown to be hard for this class [93, 94, 32, 33, 43, 77, 3 1 , 79] . Yet , the hardness of MAX S N P seemed like a weaker condition than hard­ ness for NP, and except for the chromatic number no unweighted combina­ torial problem could be shown to being hard to approximate to some degree. It hence came as a big surprise when Feige, Goldwasser, Lovasz Safra and Szegedy [50], were able to show hardness ( under a slightly weaker assump­ tion than P f:. NP ) of approximating the clique number of graphs to within constant factors. The hardness result used recent results in the area of inter­ active proofs in a very clever but simple manner, thus serving to illustrate the power of the machinery that had been built in the area of interactive proofs. Here, by showing an equally simple connection between such results and MAX SNP, we are able to show hardness results for all MAX SNP hard problems. In the following sections we will first define the notions of approximation problems and lay out the various goals that could be set for an approxima­ tion problem. In the following section we delve into the class MAX SNP and outline some of its features. We then go on to relate the notion of probabilis­ tically checkable proofs with MAX SNP. We do so by formulating the task of finding a PCP as an optimization problem in MAX SNP. The gap in the definition of PCP creates a gap in the optimization problem, which yields a hardness result even for the approximate version to this problem. 5 . 1 O ptimization problems and approximation algorith m s

The following is the definition of a NP optimization problem. Definition 5.1.1 (optimization problem) . An instance I of a NP opti­ mization problem II consists of the pair (S, value) where S represents the solution space and value : S _, � is a polynomial time computable function

referred to as the objective function. The goal of the problem maybe any one of the following: 1. Given a real number k , determine if there ea;ists a solution s such that value(s) 2: k (or value(s) � k for minimization problems).

5 . 1 Optimization problems and approximation algorithms

63

2.

Find the maximum (minimum) achievable value of value over S. This quantity is denoted OPT(!) . 3. Find the solution s E S which maximizes (minimizes) value(s) . Typi­ cally, the solution space S is of the form {0, l}n and the function value has a description length which is polynomial in n . It turns out that for many interesting problems (and in particular, the NP-complete ones) , the above three goals are equivalent under polynomial time reductions. For approximation versions of the above questions, though, the problems may not remain equivalent any more. In this chapter we will use the following notion of an approximate solution for an optimization problem. Definition 5.1.2 (approximation algorithm). An f-approximation algo­ rithm for an NP optimization problem II, takes an instance I as input and outputs an estimate E which satisfies

E < ( 1 + E)E -- < OPT l+f Notice that the above definition corresponds to the second of the three possible definitions of exact optimization problems. Note that in many appli­ cations, it would be more useful to produce an algorithm actually outputs a solution which comes close to the maximum value. But, since we are trying to prove negative results about the existence of such algorithms, proving it for the weaker notion is a stronger result . Definition 5 . 1 . 3 (polynomial time approximation scheme: P TA S ) . For a n optimization problem II , a polynomial time approximation scheme, takes a parameter f and produces an f- approximation algorithm A, for the problem II . The running time of A, on inputs of length n is bounded by a polynomial in n . (The input here is a description of the solution space S and the function f.) The research efforts of the past two decades [10, 1 1 , 1 2 , 60, 59, 95] have broadly aimed at classifying approximation versions of optimization problems into one of the following classes:

1. Fully polynomial time approximable problems: These are problems II , for which there exists a n algorithm A, such that A takes as input an instance I of II and an approximation factor f and produces as output an f-approximate estimate. The running time of A is polynomial in III and lf . 2. Problems with polynomial time approximation schemes. 3. Approximable problems: These are problems for which some constant f exists, such that an f-approximate estimate can be found in polynomial time. 4. Hard problems: These are problems for which no constant factor approx­ imation is known.

64

5. Hardness of approximations

5 . 2 MAX S N P : c o nst raint satisfaction problems

The class MAX SNP was defined by Papadimitriou and Yannakakis [93) based on the syntactic definition of NP of Fagin (45) and on subsequent definition of strict-NP due to Kolaitis and Vardi [84) . The formal definitions are presented below. Definition 5.2.1 (NP: (45) ) . A predicate II on structures I, is in NP if it

can be ezpressed in the form 3S4>(I, S), where S is a structure and 4> is a first order predicate. ( In the above definition II is equivalent to the problem and I the instance of the problem. ) Definition 5.2.2 ( SNP: (84) ) . A predicate II on structures I, is in SNP if

it can be ezpressed in the form 3S't!Xr/:>(7i, I, S), where S is a structure and 4> is a quantifier free predicate. Definition 5.2.3 (MAX SNP: [93) ) . An optimization problem II on str­

uctures I is in MAX SNP if its objective function can be expressed as max l{x : r/>(x, I, S)} l s

The following problem provides an alternate view of MAX SNP. It defines a combinatorial problem which turns out to be the "universal" MAX SNP problem. The combinatorial nature of the problem statement might make it an easier definition to use. Definition 5.2.4. A constraint of arity c is function from c boolean vari­ ables to the range {0, 1 } . The constraint is said to be satisfied by an instan­ tiation of its inputs if the boolean function evaluates to 1 at the instantiation. Definition 5.2.5 ( constraint satisfaction problem) . For a constant c, an instance I of c-CSP consists of a set of constraints C1 , Cm of arity c on variables x 1 , , :Cn where the o bjective function is • • · ,

• • •

.

max

asstgnments to

:c 1 ,

. . . , :Cn

I {Ci I Ci is satisfied by the assignment } I

The c-CSP is a universal MAX SNP problem in the sense that a problem lies in MAX SNP if and only if there exists a c such that it can be expressed as a c-CSP. The proof of this claim is straightforward and omitted. Papadimitriou and Yannakakis also introduced the notion of a linear re­ duction ( £-reduction) which is an approximation preserving reduction. The notion of £-reductions allows them to find complete problems for the class MAX SNP. Definition 5.2.6 ( linear reduction: [93] ) . An optimization problem II is

said to L-reduce to a problem II' if there exist polynomial time computable functions f, g and constant a, {3 � 0 such that

5.2 MAX SNP: constraint satisfaction problems

65

1. f reduces an instance I of II t o an instance I' of II' with the property that OPT(!) � a. OPT(I' ) . 2 . g maps solutions s ' of I' to solutions s of I such that l value'(s') OPT(I') i � .B i value (s) - OPT(!) I . It is clear from the above definition that if there is a polynomial time algorithm for II ' with worst-case error E, then there is a polynomial time algorithm for II with worst-case error a.,Bt. Using the above definition of £­ reductions, Papadimitriou and Yannakakis showed that the following prob­ lems were complete for MAX SNP. This means, in particular, that if any of the following problems has a PTAS then all problems in MAX SNP have a PTAS. MAX 3 SAT : Given a 3-CNF formula, find an assignment which maximizes the number of satisfied clauses. MAX 2 S AT: Given a 2-CNF formula, find an assignment which maximizes the number of satisfied clauses. INDEPENDENT SET- B : Given a graph G with maximum degree of any vertex being bounded by a constant B, find the largest independent set in the graph. VERTEX COVER- B : Given a graph G with maximum degree of any ver­ tex being bounded by a constant B, find the smallest set of vertices which covers all the edges in the graph. The version of this problem with no bounds on the degree of a vertex, VERTEX COVER, is hence also hard for MAX SNP. MAXCUT: Given a graph G find a partition of the vertices which maximizes the number of edges crossing the cut. Further, they show that every problem in MAX SNP is approximable to some constant factor. Lemma 5.2.1 ( [93] ) . For every pro blem II in MA X SNP, there exists a constant E such that there exists an E-approximation algorithm for II which runs in polynomial time.

Proof: We use the universality of the c-CSP. Consider a constraint optimiza­ tion problem with constraints C1 to Cm where any constraint is a function of at most c variables. Let m' be the number of constraints which are in­ dividually satisfiable i .e. , constraints for which there exists an instantiation which will satisfy them. Then r;: � OPT(/ ) � m' . Thus an algorithm that computes m' and outputs it is a 2c-approximation algorithm. D Even more interesting than problems in MAX SNP are the wide variety of problems that are known to be hard for this class. We compile here a list of few of them. TSP ( l , 2 ) : ( [94] ) Given a complete graph on n vertices with lengths on its edges, such that all edge lengths are either one or two, find the length of the shortest tour which visits all vertices at least once.

5. Hardness of appiOxima.tions

66

STEINER TR.EE(l, 2): { [32] ) Given a complete graph on n vertices with weights on its edges, such that all edge weights are either 1 or 2, and a subset S of the vertices, find the minimum weight subgraph which connects the vertices of S. SHORTEST SUP ERSTRING: ( [33] } Given a set of strings S1 , . . . , Sk i over the alphabet {0, 1}, find the leng th of the shortest string S which con­ tains all the given strings as substrings. MAX CLIQUE: { [31, 50] ) 1 Given a. graph G find the largest clique in the graph. (This problem was shown to be very hard for MAX SNP, in that if the clique size could be approximated to within n6 for any c > 0, then there exists a PTAS for MAX 3 SAT.) LONGEST PATH: { [94, 79] ) Given a graph G, approximate the length of the longest path in the graph to within any constant factor.

5 . 3 Non-exist ence of PTAS for MAX SNP hard p roblems

We now establish the hardness of approximating MAX SNP hard problems to within arbitrarily small factors of approximation. The results of this section are from the paper by Arora, Lund, Motwani, Sudan and Szegedy (S1. Consider a language L E N P and a transparent proof of membership of an input instance x in the language L. The question of deciding whether such a proof exists can be converted into an optimization problem as follows: - The space of solutions will be all possible s ( n ) bit strings, each one rep­ resenting a potential proof. Each bit of the proof will be treated as an independent variable. This creates s(n) variables denoted 1Ti . - For each poss ible random string r tossed by the tester of the tram�parent proof, we set up a constraint Tr,:z: to simulate the tester's action on the chosen random string. The constraint Tr,:z: is a specification on some 0(1) variables from t h e set {1r 1 . . . . , 1Ts(n )}· - The optimization problem which questions the existen ce of a valid proof IS:

MAX P C P : Given x E {0, 1 } n. find

Claim. MAX PCP 1

E

max

11'€ {0,1}'(�)

{ t {r\

constraint Tr,:z:

is satisfied by

1r

}\}

MAX SNP.

Berman and Schnitger (31) showed the hardness result mentioned here under the assumption that MAX 3 SAT did not have randomized PTAS. The assumption could be made weaker using some of the known derandomization techniques (say, using the idea of recycling random bits (38, 74)). The result could also be observed from the reduction of Feige, Goldwasser, Lovasz, Safra and Szegedy [50] as a

spe�:ia.l ca.se.

5.4

Discussion

67

Proof: By Theorem 4.6.1 we have NP = PCP{log n, 0{1)). Thus the number of different random strings is polynomial in the input size. Hence the number of constraints is polynomial in Ia: I. Further, since each T,.,., is a constraint on a constant number of the variables 11"i , this fits the definition of a constraint satisfaction problem and thus is a MAX SNP problem. 0 Claim. Approximating MAX PCP to within 1 0% is NP-hard.

Proof: Consider an arbitrary language L E NP and an instance a: E {0, 1}n . The MAX PCP problem deciding whether a: has a transparent proof of mem­ bership will have an optimum value of either 2r (n ) if a: E L or at most 2r (n )- l if a: ¢ L. Thus a 10% approximation to the optimum value will give an answer of at least . 9 X 2r (n ) or at most .55 X 2r (n ) . Thus even a 1 0% approximate answer suffices to distinguish between the cases :z: E L and :z: (/. L. Thus ap­ proximating MAX PCP to within 10% suffices to decide membership for any language in NP. 0 Theorem 5.3.1. For every MAX SNP-hard problem II, there exists a con­ stant f such that finding E-approximate solutions to II is NP-hard.

Proof: The proof follows from the fact that there exists an approximation

preserving reduction from MAX PCP to any MAX SNP-hard problem. particular, given any MAX SNP-hard II, there exists an f such that f-approximate solution to II would yield a 10% approximate solution MAX PCP. Thus finding f-approximate solutions to II is NP-hard.

In an to 0

5 . 4 Discussion

Addendum. The improvement in PCP technology has resulted in new hard­ ness results for several optimization problems, as well as stronger hardness results for the ones discussed in this chapter. Most notable of these are the hardness of approximation results for Chromatic Number and Set Cover, due to Lund and Yannakakis [89), the hardness of approximating many maximal subgraph problems, also due to Lund and Yannakakis [90), the hardness of 4-coloring and 3-colorable graph, due to Khanna, Linial and Safra (82) and the hardness of the nearest vector and nearest lattice point problems, due to Arora, Babai, Stern and Sweedyk (7). In almost all of these cases, hardness of approximation to within constant factors was known or could be inferred from the prior results (58, 8) - but the quality of the non-approximability results were far from the right answers. A more complete list of such hardness results may be found in the survey of Crescenzi and Kann [42) . These new results result in a much better understanding of the hardness results, at least quali­ tatively. For problems such as MAX 3 SAT, MAX 2 SAT, VERTEX COVER, MAXCUT, MAX CLIQUE , the qualitative level of approximability was re­ solved in (50, 6, 8) . However the actual constant upto which any of these

68

5. Hardness of approximations

problems can be approximated, or shown hard to approximate, is still a sub­ ject of active research. Starting with the work of Bellare, Goldwasser, Lund and Russell [28] and continuing through the works of Feige and Kilian [47] , Bellare and Sudan [25] and Bellare, Goldreich and Sudan [27] , the hardness results for all these problems have improved steadily and the best known hardness results at the time of this writeup are: MAX 3 SAT 1/38-approximation is NP-hard [28, 47, 25, 27] . MAX 2 SAT 1/97-approximation is NP-hard. [27] . VERTEX COVER 1/26 approximation is NP-hard. [27] . MAXCUT 1/82 approximation is NP-hard. [27] . SET COVER ( 1 € ) ln n-approximation is hard, for every € > 0, unless NP C RTIME (n1ogtogn ) [89, 28, 46] . MAX CLIQUE n 1 13- • approximation is hard, for every € > 0, unless NP=RP [28, 47, 25, 27] . CHROMATIC NUMBER n 1 fS-epsilon approximation is hard, for every € > 0 , unless NP=RP [89, 82, 28, 47, 25, 57, 27). -

6 . Conclusions

We have proved that any NP language admits an efficient probabilistically checkable proof of membership. This proof need only be examined in a con­ stant number of randomly chosen places by a polynomial time verifier. Cur­ rently, the transformation from the standard proof to the transparent proof requires a slightly super-quadratic blowup in size. Can this be substantially improved? We should point out that since mathematicians rarely write up proofs in enough detail to be machine checkable, our results should not be regarded as having practical consequences to mathematical proof checking. Nevertheless, it is possible that these techniques might be useful in ensuring software reliability - by making it possible to build redundancy into compu­ tations so that they can be efficiently checked. The blowup in the size of the above transformation is quite crucial for this application. One interesting consequence of our results on testing and correcting of polynomials is that we obtain efficient randomized algorithms for error­ detection and error-correction of some classical codes, like the Hadamard codes and the Reed-Solomon codes. The error-detection algorithm can very efficiently and by making very few probes into a received word, approximate its distance from a valid codeword. The error-correction algorithm can re­ trieve any bit of the nearest codeword to the received word by making very few probes into the received word. These error-detection and error-correction schemes have already been put to theoretical use in this work. It remains to be seen if they be put to practical use. The efficient randomized algorithms can be converted into fast deterministic parallel algorithms, and such error detecting and correcting schemes might be of some interest. The surprising connection between efficient probabilistically checkable proofs and the hardness of approximating clique sizes in graphs, due to Feige, Goldwasser, Lovasz, Safra and Szegedy [50] , is now much better understood. Here we showed that for every MAX SNP-hard problem, there exists a con­ stant t such that approximating the optimum value to within a relative error of t is NP-hard. More recently, Lund and Yannakakis [89] have shown strong hardness results for approximating the chromatic number of graphs and ap­ proximating the minimum set cover size for a family of sets. In the light of all these developments, it appears that this connection between probabilistically checkable proofs and approximation problems is a fundamental one. Several

70

6.

Conclusions

questions still need to be resolved including the complexity of approximating the traveling salesman problem on the plane, approximating the longest path in a graph, finding the magnification of a graph, the length of shortest vector in a lattice etc. The last of these problems is particularly interesting since the approximate version of this problem is not very sensitive to the exact norm being used, and thus a hardness under any one norm would yield a hard­ ness result under all norms. This is an example of one situation where the hardness of approximation might end up providing the first NP-completeness for even the exact problem, since the "shortest vector in a lattice" problem is not known to be NP-hard under arbitrary norms. A concrete example of such a result may be found in Lund and Yannakakis [89] , where they show the hardness of approximating a certain problem thus providing the first proof showing hardness of exact computation for that problem. The exact constant for the number of bits examined by probabilistic proof systems for NP is also very important, since this is directly related to the constants for which the different approximation problems become NP-hard. Of course, the number of bits examined can be traded off against the proba­ bility of discovering a fallacious proof. In fact, if one is willing to accept only a tiny probability of detecting a false proof, then for a certain proof system examining 3 bits of a proof is sufficient. Thus the precise version of the ques­ tion would ask: How many bits of a proof need to be examined if the verifier is expected to reject false claims with probability half? At present, the best known bound on the number of bits probed in polynomial sized proofs seems to be less than a 100 bits Phillips and Safra [96]. Such a result would translate to showing that MAX 3 SAT cannot be approximated to within 3�0• This, of course, is far from being tight (the best known upper bound for the constant is 1/8). One way of interpreting the hardness result for approximating MAX 3 SAT is the following: we need to perturb the input in a large number of places to go from "yes" instances of a problem ( one that is largely satisfiable) to "no" instances of a problem ( one in which a significant fraction of the clauses are not satisfied under any assignment). Thus the hardness of this problem is not attributable to the sensitivity to the input. An extreme form of this interpretation leads us to consider the question of whether we can draw the input from the uniform distribution ( or any polynomial time sampleable dis­ tribution} and still get problems that are very hard? Interestingly enough one of the key techniques relying on the power of polynomials - random self­ reducibility - has already been used to show instances of average case hard problems for # P by Lipton [87] . It would be interesting to see if any of these techniques can be used to show average case hardness for problems in NP. Addendum. The enormous amount of research that has one on in the areas of non-approximability and proof verification, has led to many of the questions raised above being already resolved. Polishchuk and Spielman [97] have con­ structed "nearly-linear" sized transparent proofs which are verifiable with

6. Conclusions

71

constant probes. Arora, Babai, Stern and Sweedyk [7] have also brought much better understanding to the problem of approximating the shortest vector problem, though the complexity of the problem still remains open under most norms. The value of E for which £-approximating MAX 3 SAT (or MAX 2 SAT ) is hard is getting closer to the value of € for which £­ approximating MAX 3 SAT ( MAX 2 SAT resp. ) is achievable in polynomial time. This tightening of the thresholds is a result of both improved hardness results (see discussion at end of Chapter 5) as well as the discovery of new techniques for finding approximate solutions to optimization problems and in particular the use of semidefinite programming towards this end (see the work of Goemans and Williamson [64]). Currently these threshold are within a factor of 10 from each other and the gap may well narrow further in the near future.

Bibliography

1. M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. Journal of Computer and Sys tem Sciences, 3 9 : 2 1-50, 1 9 8 9 .

2.

L. Adleman, M. Huang, and K. Kompella. Efficient checkers for number­

3.

theoretic computations. Information and Computation, 1 2 1 : 1 , 93-1 0 2 , 1 9 9 5 . S . Ar, R. Lipton, R. Rubinfeld, and M. Sudan. Reconstructing algebraic func­ tions from mixed data. Proceedings of the Thirty Third A n n u al Symposiu m on the Foundations o f Comp u ter Science, IEEE, 1 9 9 2 . Probabilistic Checking of Proofs a n d Hardness of Approximation

4. S . Arora.

Problems. PhD thesis, U.C. Berkeley, 1 9 94. 5. S. Arora. Reductions , Codes, PCPs and Inapproximability.

Proceedings of the Thirty Sixth Annual Symposium on the Fo undations of Comp u ter Science, IEEE, 1 9 9 5 .

6.

S. Arora and S . Safra. Probabilistic checking of proofs: A new characterization of NP. Proceedings of the Thirty Third Ann u al Symposium on the Fo undations

of Compu ter Science, IEEE, 1 9 9 2 . S. Arora, L. Babai, J . Stern and Z . Sweedyk. The hardness of approximat­ ing problems defined by linear constraints. Proceedings of the Tl1irty Fo urth A n n u al Symposium on the Fo unda tions of Compu ter Science, IEEE, 1 9 9 3 . 8. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof v erification and the int r act ability of approximation problems. Proceedings of the Thirty Third A n n u al Symposiu m on the Fo undations of Compu ter Scie11ce, IEEE,

7.

1992. 9.

S. Arora, R. Motwani, S. Safra, M. Sudan, and M. Szegedy. PCP and approx­ imation problems. Unpublished note, 1 9 9 2 . 1 0 . G. Ausiello, A. D ' Atri, and M. Protasi. On the structure of combinatorial problems and structure preser ving reductions. In Proceedings of the 4 th In ter­ national Colloquium on A utomata, Languages and Programming, pages 45-57, 1977. 11.

G. Ausiello, A. D 'Atri, and M. Protasi. Structure preser ving reductions among convex optimization problems.

Journal of Computer and Systems Sciences,

2 1 : 1 36-1 5 3 , 1 9 8 0 . 12.

G. Ausiello, A . Marchetti-Spaccamela, and M. Protasi. Towards a unified ap­ proach for the classification of np-complete optimiz ation problems. Theoretical

13.

L. Babai. Trading group theory for randomness.

Computer Science, 1 2 : 83-96 , 1 9 8 0 . Proceedings of the Seven teenth Annual Symposium on the Theory of Compu ting, ACM, 1 9 8 5 .

14. L. Babai. Transparent ( holographic ) proofs.

Proceedings o f the Ten th Ann u al Symposium on Theoretical Aspects of Comp u ter Science, Lecture Notes i n

C omputer Science Vol. 665, Springer Verlag, 1993.

74

Bibliography

15. L. Babai. Transparent proofs and limits to approximation. Proceedings of the First European Congress of Mathematics (1992), Vol. I, Birkhii.user Verlag, 1994, pp. 3 1-91 . 16. L. Babai and L. Fortnow. Arithmetization: A new method in structural com­ plexity theory. Computational Complexity, 1 :41-66, 199 1 . 1 7 . L . Babai and K . Friedl. On slightly superlinear transparent proofs. Univ. Chicago Tech. Report, CS-93- 1 3 , 1993. 18. L. Babai and S . Moran. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36: 254-276, 1988. 19. L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. Proceedings o f the Twenty Third Annual Symposium on the Theory of Compu ting, ACM, 1991. 20. L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1 : 3-40, 1991. 21. D. Beaver and J . Feigenbaum. Hiding instances in multioracle queries. Proceed­ ings of the Seven th Annual Symposium on Theoretical Aspects of Compu ter

22. 23. 24. 25. 26. 27.

28.

29. 30. 31. 32.

Science, Lecture Notes in Computer Science Vol. 415, Springer Verlag, 1990. D. Beaver, J . Feigenbaum, J. Kilian, and P. Rogaway. Security with low com­ munication overhead. In Proceedings of Crypto '90, Springer Verlag LNCS 537, pages 62-76, 1991. M. Bellare. Interactive proofs and approximation: reductions from two provers in one round. Proceedings of the Second Israel Symposium on Theory and Compu ting Systems, 1993. M. Bellare and P. Rogaway. The complexity of approximating a nonlinear program. Complexity of Numerical Optimization, Ed. P.M. Pardalos, World Scientific (1993 ) . M. Bellare and M. Sudan. Improved non-approximability results. Proceedings of the Twen ty Sixth Annual Symposium on the Theory of Compu ting, ACM, 1994. M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi and M. Sudan. Linearity test­ ing in characteristic two. Proceedings of the Thirty Sixth Annual Symposium on the Foundations of Compu ter Science, IEEE, 1995. M. Bellare, 0 . Goldreich and M. Sudan. Free bits, PCP and lnapproxima­ bility: Towards tight results. Proceedings of the Thirty Sixth Ann u al Sym­ posium on the Foundations of Compu ter Science, IEEE, 1995. Full ver­ sion avaliable from the Electronic Colloquium on Computational Complexity, http : //www . eccc . uni-trier . de/eccc/. M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs. Proceedings of the Twen ty Fifth Ann u al Symposium on the Theory of Compu ting, ACM, 1993. (See also Errata sheet in Proceedings of the Twen ty Sixth Annual Symposium on the Theory of Compu ting, ACM, 1994 ) . M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover inter­ active proofs: How to remove intractability assumptions. Proceedings of the Twentieth Ann ual Symposium on the Theory of Comp u ting, ACM, 1988. E. Berlekamp and L. Welch. Error correction of algebraic block codes. US Patent Number 4,633 ,470, 1986. P. Berman and G. Schnitger. On the complexity of approximating the inde­ pendent set problem. Information and Computation, 96:77-94, 1992. M. Bern and P. Plassman. The steiner problem with edge lengths 1 and 2. Information Processing Letters, 32:1 71-1 76, 1989.

Bibliography

75

33. A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings. Proceedings of the Twenty Third A n n u al Symposium on the Theory of Compu ting, ACM, 1991. 34. M. Blum. Designing programs to check their work. Tech nic al Rep ort TR-88009, International Computer S cience Ins tit u t e 1 988 . 35. M. Blum and S. Kannan. Program cor rec tness checking . . . and the design of programs that check their work. Proceedings of the Twenty First Ann u al Symposium on the Theory of Compu ting, ACM, 1989. 36. M. Blum, M. Luby, and R. Rubinfeld. Self test ing /correc t in g with applic ations to numerical problems. Journal of Computer and Sys tem Sciences, 47:3, 1993. 37. J.Y. Cai, A. Condon, and R. Lipton. PSPACE is Provable by Two Provers in One Round. Proceedings of the Sixth A n n u al Conference on Structure in Complexity Theory, IEEE, 1991. 38. A. Cohen and A. Wigderson. Dispersers , det erministic amplific ation , and weak random sources. Proceedings of the Thirtieth An11 ual Symposium 011 the Fo ull­ d ations of Compu ter Scie11ce, IEEE, 1989. 39. A. Condon. The complexity of the max word problem , or the power of one-way ,

-

interactive proof systems.

Proceedi11gs of tl1e Eigh th A n n u al Symposium on

Lecture Notes in Computer Science Vol. 480, Springer Verlag, 1 9 9 1 . 40. A. Condon , J . Feigenbaum, C. Lund and P . Shor. Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions. Theoretical Aspects of Comp u ter Science,

Proceedings of the Twenty Fiftl1 Ann u al Symposi u m on tl1e Tl1 eory of Com­ p u ting, ACM, 1993.

41. S . A . Cook. The complexity o f theorem proving procedures.

Proceedings o f the

ACM, 1 9 7 1 . 42. P . Crescenzi and V . Kann. A compendium o f N P optimization prob­ lems. Manuscript avalible from the authors, p i luciDds i . uniroma l . it or [email protected]. 43. E . Dalhaus, D.S. Johnson , C.H. Papadimitriou, P.D. Seymour, and M. Yan­ nakakis. The complexity of multiway cuts. SIA M Journal on Computing, 23:4, Third A n n u al Symposium on the Theory of Comp u ting,

pp. 864-8 94, 1 994. 44. W. F De la Vega and G.S. Lueker. Bin Packing can be solved within 1 + f in Linear Time. Combinatorica, vol. 1, pages 349-3 55, 1 9 8 1 . 4 5 . R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIA M-A MS Proceed­ ings, Vol. 7, pages 43-73, 1 974. 46. U. Feige . A threshold of In n for approximating set cover. Manuscript, 1 995. 47. U. Feige and J . Kilian. Two prover protocols - Low error at affordable rates. .

Proceedings of the Twenty Sixth A n n u al Symposium on the TJ1eory of Com­ p u ting, ACM, 1 994.

48. U . Feige and L . Lovasz. Two-prover one-round proof systems: Their power and their problems.

Proceedings of the Twen ty Fo urth A1w u al Symposi um on the Theory of Comp u ti11g, ACM, 1 992.

49. U. Feige and C . Lund. On the hardness of computing the permanent of random matrices.

Proceedings of the Twenty Fo urth A mJ U al Symposium on tl1e TJ1eory of Comp u ting, ACM, 1992.

50. U. Feige, S. Goldwasser, L . Lovasz , S . Safra, and M. Szegedy. Approximat­ ing clique is almost NP-complete. Proceedings of the Thirty Second An11 u al Symposium on the Fo u11dations of Com p u ter Sciei1 ce, IEEE, 1 9 9 1 .

5 1 . J . Feigenbaum. Locally random reductions i n interactive complexity theory. In J. y. Cai, editor, Complexity Theory, DIMA CS Series on Discrete Mathematics and Theore tical Computer Science,

1 993.

76

Bibliography

J. Feigenbaum and L. Fortnow. On the random self-reducibility of complete sets. Proceedings of the Sixth AmJ U al Conference on Struct ure in Complexity Theory, IEEE, 1 9 9 1 . 5 3 . L. Fortnow, J. Rompel, and M. Sipser. On the power o f multi-prover inter­ active protocols. Proceedings of the Third Ann u al Conference on Struct ure in Complexity Th eory, IEEE, 1988. 54. K . Friedl, Zs. Hatsagi and A. Shen. Low-degree testing. Proceedings o f the Fifth Symposium on Discrete Algorithms, ACM, 1 994. 55. K. Friedl and M. Sudan. Some improvements to low-degree tests. Proceedings

52.

of the Third Israel Symposium on Theory and Compu ting Systems,

1995 .

56. R. Freivalds. Fast probabilistic algorithms. In Lecture Notes in Computer Science, pages 57-69. Springer-Verlag, 1979. 57. M. Furer. Improved hardness results for approximating the chromatic number.

Proceedings of the Thirty Sixth Annual Symposium on the Fo undations of

Compu ter Science, IEEE, 1995. 58. M.R. Garey and D.S. Johnson. The complexity of near-optimal graph coloring.

Journal of the A CM,

23:43-49, 1976.

59. M.R. Garey and D.S. Johnson. "strong" NP-completeness: Motivation, exam­ ples and implications. Journal of the A CM, 25:499-508, 1 978. 60. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, 1 979. 61. M. Garey, D . Johnson and L . Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science 1 , pp. 237-267, 1976. 62. P. Gemmell and M. Sudan. Highly resilient correctors for polynomials. Infor­ mation Processing Letters 43

(1992), 1 69-174.

63. P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self­ testing/correcting for polynomials and for approximate functions. Proceedings of the Twenty Third Ann u al Symposium on the Theory of Compu ting, ACM, 1 99 1 . 64. M. Goemans and D. Williamson . . 878 approximation algorithms for Max-CUT

and Max-2SAT.

Proceedings of the Twen ty Six th Ann ual Symposium on the Theory of Compu ting, ACM, 1994.

65. 0. Goldreich. A taxonomy of proof systems. In SIGACT News complexity theory column 4, SIGACT News Vol. 25, No. 1 , 1994. 66. 0. Goldreich. Probabilistic proof systems. Proceedings of the In tern ational Congress of Mathematicians, 1994. 67. 0. Goldreich and L. Levin. A hard-core predicate for any one-way function. Proceedings of the Twen ty First Ann ual Symposium on the Theory of Com­

ACM, 1989. 68. 0. Goldreich, S. Micali, and A. Wigderson. p u ting,

Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. Proceedings of the Twen ty Seventh Ann u al Symposium on the Fo undations of Comp u ter Science, IEEE, 1986.

69. 0. Goldreich, R. Rubinfeld and M. Sudan. Learning polynomials with queries: The highly noisy case. Proceedings of the Thirty Sixth Ann u al Symposium on the Fo undations of Computer Science, IEEE, 1995. 70. S. Goldwasser, S . Micali, and C. Rackoff. The knowledge complexity of inter­ active proof systems. SIA M Journal on Computing, 1 8 : 1 86-208, 1989. 7 1 . D.S. Hochbaum and D.B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Res earch, 10(2):180-184, May 1985. 72. D.S. Hochbaum and D.B. Shmoys. A unified approach to approximation al­ gorithms for bottleneck problems. Journal of the A CM, 33(3): 533-550, July 1986.

Bibliography

77

73. D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the A CM, 34(1): 144-162, January 1 987. 74. R. lmpagliazzo and D. Zuckerman. How to recycle random bits. Proceedings of the Thirtieth Ann u al Symposium on the Fo undations of Comp u ter Science,

IEEE, 1989. 75. D. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and Systems Sciences, 9 ( 1974), 256-278. 76. D. Johnson. The NP-completeness column: an ongoing guide. Journal of A lgo­ rithms, 1 3 , 1992. 77. V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters, 37:27-35 , 1991. 78. S . Kannan. Program Result Checking with Applications. PhD thesis, University of California, Berkeley, 1 990. 79. D. Karger, R. Motwani, and G.D.S. Ramkumar. On approximating the longest path in a graph. Proceedings Workshop on A lgorith ms and Data Structures, Lecture Notes in Computer Science ( Springer-Verlag ) , vol. 709, pp. 42 1-430 , 1993. 80. R.M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Ple nu m Press, 1972. 81. N. K armakar and R.M. Karp. An Efficient Approximation Scheme For The One-Dimensional Bin Packing Problem. Proceedings of the Twer1 ty Third An­ n u al Symposium on the Fo u n dations of Comp u t er Science, IEEE, 1982.

82. S. Khanna, N. Linial and S. Safra. On t h e hardness o f approximating the chromatic number.

Proceedings of tl1e Second Israel Symposium 011 Tl1eory

1993. 83. S . Khanna, R. Motwani, M. Sudan and U . Vazirani. On syntactic versus com­ and Comp u ting Systems,

putational views of approximability.

Proceedings of tl1e Thirty Fifth Ann u al Symposiu m on the Fo u n dations of Comp u ter Science, IEEE, 1994.

84. P. Kolaitis and M. Vardi. The decision problem for the probabilities of higher­ order properties.

Proceedings of the Nin eteenth A n n u al Symposi um on tl1e

ACM, 1987. 85. D. L apidot and A. Shamir. Fully parallelized multi prover protocols for NEX­ Theory of Comp u ting,

PTIME.

Proceedings of the Thirty Second Ann ual Symposi um on tl1e Fo un­ dations of Compu ter Science, IEEE, 1 9 9 1 .

8 6 . L. Levin. Universal'ny!e pereborny!e zadachi ( Universal search problems, in Russian ) . Problemy Peredachi Informatsii, 9:265-266, 1973. A corrected En­ glish translation appears in an appendix to Trakhtenbrot [109]. 87. R. Lipton. New directions in testing. In J . Feigenbaum and M. Merritt, editors, Distributed Computing and Cryp tography, DIMA CS Series in Discrete Math

and Theore tical Computer Science, A m e rican Mathematical Society, 2 : 1 9 1-202, 1991. 88. M. L uby. A simple parallel algorithm for the maximal independent set problem. SIA M Journal of Computing, 1 5(4) : 1 036-105 3 , 1986. 89. C. Lund and M . Yannakakis. On the hardness of approximating minimization problems. Preprint, June 1992. 90. C . Lund and M . Yannakakis. The approximation of maximum subgraph prob­ lems. Proceedings of ICALP 93, Lecture Notes in Computer Science Vol. 700, S prin ge r Verlag, 1 99 3 . 9 1 . C . Lund, L . Fortnow, H . Karloff, and N. Nisan . Algebraic methods for inter­ active proof systems. Proceedings of the Thirty Firs t A n n u al Symposiu m on the Fo u n d a tions of Compu ter Science, IEEE, 1990.

78

Bibliography

92. R. Motwani. Lecture Notes on Approximation Algorithms. Technical Report, Dept. of Computer Science, Stanford University ( 1992 ) . 93. C. Papadimitriou and M. Yannakakis. Optimization, approximation and com­ plexity classes. Journal of Computer and System Sciences, 43:425-440, 1991. 94. C. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Journal of Mathematics of Operations Research, 1992. 95. A . Paz and S. Moran. Non-deterministic polynomial optimization problems and their approximation. Theoretical Computer Science, 1 5:251-277, 1981. 96. S. Phillips and S. Safra. PCP and tighter bounds for approximating MAXSNP. Manuscript, Stanford University, 1992. 97. A. Polishchuk and D. Spielman. Nearly Linear Sized Holographic Proofs. Pro­ ceedings of the Twenty Sixth Annual Symposium on the Theory of Compu ting,

ACM, 1 994. 98. R. Raz. A parallel repetition theorem.

Proceedings of the Twenty Seven th

ACM, 1995. 99. I.S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society of Industrial and Applied Mathematics, 8: 300-304, June 1960. 100. R. Rubinfeld. A Mathematical Theory of Self- Checking, Self- Testing a n d Self­ Correcting Programs. PhD thesis, University of California at Berkeley, 1990. 1 0 1 . R. Rubinfeld and M. Sudan. Testing polynomial functions efficiently and over rational domains. Proceedings of the Third Symposium on Discrete Al­ gorithms, ACM, 1 994. 102. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials and their applications to program testing. To appear in SIA M Journal on Computing. Technical Report RC 1 9 1 56, IBM Research Division, T. J. Watson Research Center, P.O. Box 2 1 8 , Yorktown Heights, NY 1 0598, September 1993. 103. S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the A CM, 23:555-565, 1 976. 104. J . Schwartz. Fast probabilistic algorithms for verification of polynomial iden­ tities. Journal of the A CM, 27:70 1-71 7, 1980. 105. A. Shamir. IP PSPACE. In Proceedings of the 3 1 s t A nnual IEEE Symposium on Foundations of Computer Science, pages 1 1-15, 1990. 106. A. Shen. Personal Communication, May 1 9 9 1 . 1 0 7 . D. Shmoys. Computing near-optimal solutions t o combinatorial optimization problems. In W. Cook, L. Lovasz, and P. D . Seymour, Editors, DIMACS vol­ ume on Combinatorial Optimization, 1995. 108. G. Tardos. Multi-prover encoding schemes and three prover proof systems. A n n u al Symposium on the Theory of Compu ting,

=

109. llO.

Proceedings of the Ninth Annual Conference on Struct ure in Complexity The­ ory , IEEE, 1994. B.A. Trakhtenbrot. A survey of Russian approaches to perebor ( brute-force search ) algorithms. A nnals of the History of Computing, 6:384-400, 1984.

van der Waerden. A lge bra, volume 1. Frederick Ungar Publishing Co. , Inc., 1970. l l l . M. Yannakakis. On the approximation of maximum satisfiability. Proceedings of the Third Symposium on Discrete Algorithms, ACM, 1994. ll2. D. Zuckerman. NP-Complete Problems have a version that is hard to Approx­ imate. Proceedings of the Eigh th Ann ual Conference on Structure in Complex­ ity Theory, IEEE, 1 993.

A . The Berlekamp Welch decoder

The essence of the Berlekamp Welch technique lies in their ability to use rational functions to describe a sequence of points most of which lie on a univariate polynomial. We first give some basic facts about rational functions.

In this section, we can allow these functions to be functions over any field F . A . l Preliminaries : rational fu nctions

Definition A . l . l (rational function) . A function r : F ----> F is a rational function if it can be expressed as r( x) = for polynomials f and 9. The degree of r( x) is given by the ordered pair ( d1 , d2) , where d1 is the degree of f( x ) and d2 is the degree of g ( x ) .

�

Definition A .1.2. A rational function r(x) describes a sequence i = 1 to n} if for all i , Yi = r(xi) or r(xi) evaluates to OjO.

{ (xi, Yi ) l

Fact A . l . l (uniqueness) . If rational functions 9h1 (Xx)) and h( ( x)) both of de92 X gree (d 1 , d2) where d 1 + d2 < n describe a given sequence {(xi, Yi )li = 1 to n } ,

then b.. 91

=

12 . 9>

Proof {Sketch}: Follows from the fact that the polynomials h * 92 and h * 9 1

agree at each of the points Xi· But these are both polynomials of degree d 1 + d2 and if they agree at n > d 1 + d2 points, then they must be identical. 0 Hen c e b.. = 12 . 91 9>

Fact A.1.2 (interpolation) . Given a sequence {(xi , Yi )li = 1 to n}, a ra­ tional function of degree (d 1 1 d2) that describes the given sequence can be found in time polynomial in n, provided one exists.

Proof: Observe that if we let the coefficients of f and 9 be unknowns, then

the const r aints f( Xi) = Yi * 9( Xi ) become linear constraints in the unknowns. Thus if the linear system so obtained has a solution, then it can be found by matrix inversion. 0

80

A . The Berlekamp Welch decoder

A . 2 The decoder

Recall that the task we wish to solve is the following: Given : n points { ( xi , Yi ) li = 1 to n} . Output : A polynomial p of degree at most d such that for all but k values of i, Yi = p( xi ) {where 2 k + d < n}.

Claim. There exists a rational function the given sequence.

r

of degree ( k + d, k) which describes

Proof: Consider a polynomial W which evaluates to zero at Xi if Yi :f. p(Xi). It is clear that such a polynomial with degree is at most k exists. Now consider the rational function � . This describes all the input points. 0 We are now in a position to prove Lemma 2 . 3 . 1 : Lemma 2 . 3 . 1 Given n points (:z:i , Yi ) E F2, there exists an algorithm which finds a degree d polynomial g such that g ( xi ) = Yi for all but k values of i, where 2k + d < n, if such a g exists. The running time of the algorithm is polynomial in d and n. Proof: Claim A.2 tells us that there exists a rational function of the form a:;- which describes the given points. A rational function which describes the given points can be found by interpolation and the rational functions are unique except for multiplication by common factors, and thus are of the form a:,' . Thus the quotient of the so obtained rational function gives us g. 0

B . Composing proof systems

Here we prove Lemma 4.3. 1 . Recall the definition of rPCP. We wish to prove:

Lemma 4.3.1 If NP C rPCP(rt (n) , q1 (n)) and NP C r PCP (r2 (n), q2(n)) , then N P C r PCP (r t (n) + r2(q1 (n) ) , q2(q1 (n) ) ) .

Proof: The proof follows in a straightforward manner based o n the discussion

of Section 4.3. The proof is somewhat long since we have to ensure that the composed system satisfies all the properties required of an rPCP proof

system.

Input Encoding. Let E1 be the coding scheme for the rPCP ( r1 ( n ) , q1(n)) proof system and let E2 be the coding scheme for the r P C P ( r 2(n) q2(n)) proof system. Then the coding E for the composed proof system is obtained by first encoding x according to E1 and thus obtaining a s1 ( n) X q1 ( n) table T1x and then encoding each q1(n)-bit entry of T1x as a s2 (q1(n)) X q2(q1(n) ) entry. The final table for x thus contains s1 (n) X s2 (q1 (n) ) entries each of which is q2(q1(n) ) bits long. The inverse mapping E- 1 is obtained by viewing a table T : [s1 ( n )] x [s2(q1 (n))] -> {0, l}q,(q.(n)) as s1 (n) tables of size s2 (q1(n)) X q2(q1 (n)) and 1 inverting each of these tables according to E2 . This gives s1 ( n) entries of size q1(n) which can be viewed as a s1 (n) x q1 (n) table which when inverted 1 according to E! gives an n-bit string. This n bit string is defined to the inverse according to E- 1 of the table T. ,

Proof Tables. Let 1r1x be the proof table for

x

E

L according to the

rPCP ( r1 ( n ), q1 ( n)) proof system. Then the first portion of the proof table 1r for the composed system consists of s1 ( n) tables of size s2 ( q1 ( n)) x q2 ( q1 ( n) ) . These are the tables obtained by encoding each entry of 1r 1x according to E2 .

The second portion of 1r consists of one table for each possible random string r E {0, 1 Y,(n). Let Yl , · · · , Yc ' be the contents of the c' locations of the tables E1 ( x t ) , . . , E1 ( X c ) and 1r1 that are read by the tester T1 on the choice of r as a random string. Further, let Cr be the circuit of size poly ( q1 ( n)) which decides whether to accept YI . · · · , Yc' or not. Then the table 1r contains a table 1r2r of size s2 (q1(n)) X q2(q1 (n) ) which proves that (Cr , Yl , . . . , yc' ) represents a circuit with an accepting input assignment in y1 · · · Yc ' · ( Notice that this is a polytime computable predicate and hence in NP. ) .

82

B . Composing proof systems

Tester. The tester T for the composed proof system acts as follows. It first picks a random string r E {0, lY' (n ) and tries to simulate the action of the tester Tt . This would involve reading y1 1 • • • , Yc' and then verifying that a circuit Cr will accept (Yt , . . . , Yc' ) . The tester will thus encode the represen­ tation of the circuit Cr using E2 and then use the second proof system and the proof 11'2r to verify that E2( Cr ), E2(yl ), . . . , E2 (Yc• ) represents a circuit with an accepting input assignment. Notice further that the computation of the tester T can be expressed as a circuit of size poly (q2(q1(n) 0 ( 1 l )) (which is the same circuit which describes the computation of tester T2 on input E2( Cr ), E2(yi ), . . . , E2(Yc' ) and proof 11'2r ). Correctness. It is clear that if :z: 1 · :z: 2 · · · :Z:c E L then there exists a proof such that the tester T always outputs PASS. For the other direction, consider 1 tables T1t , Tc such that E- ( r1 ) · · · E- 1 ( Tc ) f:. L. Let 1r be a proof which 1 tries to prove that E- ( ri ) · · · E- 1 ( Tc ) E L. We will show that the tester T will output FAIL on this proof with probability at least 1/4. 1 Let rP> , . . . , r£ > be the s 1 ( n) X q1 ( n ) tables obtained by interpreting the tables T1 t . . . , Tc as s1 ( n) tables of size s2 ( q1 ( n)) X q2( q1 ( n ) ) and decoding 1 each such table according to E:; . Similarly let 1r1 be the s1 ( n) x q1 ( n ) table obtained by decoding the tables of the first half of 1r according to Then 1 1 c E1 (r� 1 ) ) · E1 (r� ) ) f:. L. Therefore we find that for half the choices of r E 1 1 c {0, lY' ( n ) , the tester T1,r (E1 (rp > ) · E1 (ri >), 1r i ) will output FAIL. Now for all such choices of r, Let the contents of the entries of r1 , . . . , Tc and 1r1 as read by the tester T1 be Y1 t . . . , Yc' · Then, Y1 , . . . , Yc• are the inverse encodings of 2 1 some tables ri ), , tau�;> according to E:; • Tt,r (Yt , . . . , Yc' ) outputs FAIL, By the property of the second proof system, we have that for at least half 2 the choices of r ( 2 ) E {O, lY> ( q, (n )) , the tester T2 , r C>) (rf >, . . . , tau�7>, 11'2 will output FAIL for any proof 1r2• Thus with probability 1/4 the tester T outputs fail on any proof 1r. By running the same tester thrice on this proof system, the probability of outputting fail can be increased to 37/64 which is greater than a half. • • •

• • •

0

C . A characterization of NP via polynomial

sequences

We first show how to construct a sequence of polynomials which verifies that a 3-CNF formula is satisfiable. Lemma 4.2.1 ( [20, 19] ) For a 3-CNF formula ,P there exists a polynomial sequence of length and width at most log n, with polynomials of degree at most log 2 n in 8( 10101�;n ) variables, such that sequence can be terminated in the trivial polynom� al if and only if ,P is satisfiable. Proof: The proof places the formula ,P and the assignment A in a suitable encoding and then verifies the consistency of A for ,P. To encode n-bits a 1 , . . . , a n which represent an assignment to n variables, we will use the ( m, h, F)-polynomial extension encoding, where h= = n . Recall that this means that we pick a set II C F (with I II I = h) and let A be the function from JI= to {0, 1 } which is specified on n places by a 1 , . . . , an · The encoding is the extension of A to a low-degree polynomial A (of degree at most mh). The encoding of the 3-CNF formula is obtained as follows: We view the formula as a function f from H 3m x {0, 1 P to {0, 1 } , where f(z1 , z2 , z3, b1 , b2, b3) = 1 if the formula has a clause whicL contains the variable z1 , z2 , z3 with negated variables indicated by the bit b; being 1. The encoding of this formula will be a function j : F 3m + 3 __, F . Consider the function sat? : F 3m + 3 --> F defined as follows: 3 sat ?(z1 , z2 , z3, b 1 , b2 , b3) = IJ (A(zi ) * b; + ( 1 - A(zi ) ) * ( 1 - bi ) ) i= l sat? is a polynomial of degree O ( m h ) and evaluates to zero in the domain H 3'"' x {O, lP if the clause given by (z1 , z2 , z3, h , b2 , b3) is satisfied by the assignment. Now consider the polynomial g ( 0) (z1 , z2 , z3 , b1, b2, b3)

f(z l , z2 , z3, b1 , b2, b3)

sat ? (z1, z2 , z3 , h , b2 , b 3) Our task is to ensure that g(o) is zero on the domain II 3m x {0, 1 p. Let m' = 3m + 3 . g(o ) is a function on m' variables, say z1 , . . . , Zm ' , and we wish to ensure that g restricted to Jim ' is zero. We do so by constructing a sequence of polynomials such that the final polynomial will not be zero if the initial one is not zero on this subdomain. The intuition behind the rest of this =

*

C. A characterization of NP via polynomial sequences

84

proof is as follows. Effectively we want to simulate the effect of an OR gate which has fanin Hm' 1 by a polynomial sequence with small width and length. So first we implement the OR gate with fanin Hm' by a circuit of depth m' and in which each gate has fanin H (in the obvious way). Then we show how to implement each OR gate in this circuit - approximately - by a low degree polynomial. This leads to a polynomial sequence whose width is the fanin of the circuit and whose length is the depth of the circuit. The polynomial g(i ) is a function of the variables Zi + l ! . . . , Zm • and w11 . . . , Wi and is defined as follows:

(where ( is some function that maps the elements in H to distinct integers in the range 0, . . . , h - 1). It is clear that the g( i ) •s are polynomials of degree O(h) in each variable. To complete the argument we wish to show that g(m' ) identically becomes zero if and only if g(o) is zero on the domain Hm' . Let r11 . . . , rm • be randomly chosen from F. We will show that g( i ) ( zi+ 1 • . · h h tgh probab·1· , Zm ; r1. . . . , ri ) 1s non-zero wtt 1 tty, 1· f g (i - 1 )( y, Zi+ 1 , . . . , Zm• ; ' l r1, . . . , ri - 1) is non-zero for any y E H. Let Cy = g(i - )(y, zi+1 · · · · · Zm • i r1 , y . . . . . . , r• - 1 ) · Then g ( i ) ( z•+ l ! · · · · Zm • ·, rl > · · · • w• ) a umvan-" wy E H Cy * Wi( ( ) , ts ate polynomial of degree h in Wi whicp is not identically zero. Thus for a ran­ dom choice of Wi = ri the summation is non-zero with probability 1 - h/ I F I . Conversely, also observe that if the cy ' s are all zero then the weighted sum is zero. This gives us the "approximate" OR gate we were looking for. By a simple argument, it can now be shown that with probability 1 - m'h/ I F I , g(m')(r11 . . . , rm ) i s non-zero, i.nplying that g(m' ) i s not identically zero. ' Thus we have shown how to build a construction sequence A,sat?, , g(m' ) with the property that 3A such that g(m' ) = 0 if and only g(0) , if f represents a satisfiable 3-CNF formula. Observe further that the length, width and degree of the sequence is as promised. 0 Now we are in a position to show a stronger version of this lemma: i.e., where the inputs are themselves part of the sequence. We will let the inputs , :Cc be encoded by the (m, h, F)-polynomial extension code Em , h , F · :c 1 1 The decoder E;;,\, F finds the closest polynomial to a function f : Fm --+ F and uses its values on the space Hm as the message. (Observe that the mes­ sage so obtained is a message from I F in and not necessarily {0, 1 }n. Since L will only include strings from {0, 1 }n, we will have to exclude all the remain­ ing strings explicitly.) Theorem 4.4.1 Given a constant c > 0 and language L E NP and a pa­ , log n )-construction rule for degree log 2 n polynomi­ rameter n, a ( 1 n als g<0), , g(l) where g(i ) : Fm --+ F, can be constructed in polynomial time, with the property that 3g(o) s.t. g(l) = 0 ¢:> :c1 :c 2 :C c E L, where . • .

·

·

·

·

• • •

• • •

�;��;

• • •

•

•

•

•

C. A characterization of NP via polynomial sequences

85

n :Z:i E F is the decoding according to E;;/· h • F of the polynomial g(i). Moreover I F I = O ( polylog n ) and m = e( ,;o,�;n ). 1 Proof: The proof follows from th: following basic ideas:

- ( Cook's Theorem) Given c, n and L we can construct a 3-CNF formula 4>n on n' = en + n°(l) such that 3y such that 4>n (a: l , :z: 2 , , :Z: c , y) is true if and only if :z:1 :Z: c E L. - (Assignment) Let g(o) be the Em, h,F encoding of the assignment to y. Let g(i) be the encodings of :Z:i . Construct g( c + l ) : Fm + l -+ F to be g( c+ l ) ( i, z) = g(i ) (z). We will name this the assignment function A . . • •

•

• •

Now we are in a position to apply the lemma described above and construct a sequence of polynomials g( c + 2 ) , , g(l) such that the final polynomial is zero if and only if the assignment given by A satisfies 4>n · • • •

0

1 Some attributional remarks: Most of the technical work required for this theorem was done by Babai, Fortnow and Lund [20] , but their characterization refers specifically only to NEXPTIME languages. The works of B abai, Fortnow, Levin and Szegedy (19] and Feige, Goldwasser, Lovasz , Safra and Szegedy [50] scale down the (20] proof to NP languages. In order to scale down this result B abai, Fortnow, Levin and Szegedy (19] needed more compressed representations of the assignment function than found in the encoding used by B abai, Fortnow and Lund [20] . They were the first to use the particular size of H as used in the proof here. The observation that one could work with a constant number of encoded inputs is made by Arora and Safra [6] .

Index

approximation 63 approximation by polynomials 46 approximation preserving reductions 61 checker 6 , 9 close 1 5 constraint satisfaction problem curve 1 6 , 1 8 distance 2 - absolute 9 - between functions - relative 9 - to function family

15 8

encoding scheme 5 1 , 52, 55 error-correction 9 error-detection 9 evenly spaced points 26 evenly spaced test 29, 31 Hadamard Codes 1 0 hardness of approximation - chromatic number 6 1 - clique size 14, 62 - MAX SNP 14, 67 L-reduction 62, 64 linear corrector 54 linearity 8, 53 linearity testing 54 lines 1 6 , 34 LONGEST PATH 66 MAX 2 SAT 65 MAX 3 SAT 65 MAX CLIQUE 66 MAX CUT 65 MAX PCP 66 MAX SNP 14, 6 2 , 64-67

64

neighborhood 3, 23, 24 neighborhood constraint optimization problem oracle 4, 1 2

24

62

pairwise independence 2 0 PCP 49, 62 permanent 9 , 22, 41 polynomial - construction rule 5, 40, 50, 52, 84, 85 -- satisfiability 5 , 43 - distance 2 - implicit 23 - random self-reducibility 17 - reconstruction 21 - self-correction 2, 1 1 - - multivariate 21 , 4 1 - - univariate 18 - testing 3, 23 specific 40 - univariate 25 -- with help 4, 42 Polynomial Evaluation Codes 1 1 Polynomial Extension Codes 1 1 , 52, 84 proof 1 - interactive 1 2 multiprover interactive 8, 1 2 , 58 probabilistically checkable 1 , 1 3 , 48 transparent 12, 48 prover 4 PTAS 63 -

query complexity

1 3 , 49, 57

random self-reducibility 8, 16, 22 randomness complexity 1 3 , 49 recursive proof checking 50, 53, 57, 8 1 Reed Solomon Codes 1 0

Index resilience 1 5 rPCP 5 1 , 5 3 , 57, 8 1 segmented proofs 5 0 , 5 1 self-corrector 1 , 7, 1 6 self-tester 1 , 7 self-testing/correcting - function family 8 SHORTEST SUPERSTRING SNP 64 STEINER TREE 66 TSP(1 ,2)

65

verifier 1, 4 - probabilistic

12

VERTEX COVER

65

66

87

Lecture Notes in Computer Science

For information about Vols. 1 - 954

please contact your bookseller or Springer- Verlag

V()J. 955: S.G. Akl, F. Dehne. J.-R. Sack, N. Santore. (Eds.). Alg()rithmg a11d DMa Slrunures. Proceeding<, 1995. IX, 5 ! 9 pages. 1 995.

VoL 973: H.H. Adelsberger . J . Laiansky, V. M arfk (Ed<.), lnformation M anag eme nt >n C o mpu ter Integrated Manuf;;cturing. IX, 665 pages. ! 995.

pu(ation. Proceedings,

Image Analysis and Processing Proceedings, 1 995. XIX,

Vol.

956:

X. Yao (Ed. ) Pragre33 in Evolutionary Com­

(:lubseries LNAI).

, 1993 , 1 994. VIII, 3 1 4 pages.

1995.

VoL

9 74 : C.

Braccini,

L DeFloriam, G.

Vernazza (Eds.).

757 pages. 1995.

Luk (Eds.), Field-Programmable

Vol. 9 5 7 : C. Castelfranchi, 1.-P. Miiller (Eds.), From

Vol. 975: W . Moore, W .

Reaction to Cognition. Proceedi ngs, 1 993. VI, 252 pages.

Logic and Applications. Proceedings , 1995. XI, 448 pages.

1995. (Subseries LNAI).

1 995.

VoL

V oL 976: U . Montanari , P.

9 5 8 : J. Calmet, J . A. C�mpbell (Eds.), Integrating

S y m b o l i c Mathematical

ln!elllgwee. Proceeding<.

VQI 9 59 :

D . -Z. Du,

CDmputotion and Artificial 1 994. X . 275 pages. 1 995.

M Li ( E d s . J , Computing artd 1 995 XIII, 654 pages. 1 99 5 .

CQmbinatorics. Proceedings.

Rossi

(Eds.), Principles and

of C o nstra i n t 1'1 o g r • m m i n g -

Pr a c t i c e

Pwceedjngs, Vol 977:

1 995. XIII . 65 1

H . Beilne' . F

p�gcs 1 995.

B a u se

CP

' 95 .

(Eds.),_ Qu an tita u vc

E v a l\Jation of Computing and Communication System<.

V o l . 9 6 0 : D . Leivant ( E d . ) , Logic a n d Computational

Proceedings, 1 99 5 . X , 4 1 :5 pages. 1 9 9 5 .

Complexity. Proceedings, 1 994. Vlll, 5 1 4 pages. 1 99 5 .

V o l . 9 7 8 : N . Revell, A M . TJoa (Eds . ) , Database and

V o l . 96 1 : K . P . Jantke, S . L a n g e (Eds . ) , Algorithmic Learning for Knowledge-Based Systems. X , 5 1 1 pages. 1 995. (Subseries LNAl). V ol . 962: L Lee, S . A .

V o L 9 7 9 : P . Spirakis ( E d . ) . Algorithms - E S A ' 9 5 .

&mDlko

(5ds.), CONCUR ' 9 5 :

Concurrency Theory. l'rDceedmgs. 1 99 5. X, 5 4 7 page<

1 995.

Vol 9G3:

). Advances in Cryptol<Jgy 1 99 5 . XII, 467 pages. 1 99 5 .

D. Coppersmirh (Ed

- CRYPTO '95. Proceeding<.

V o l . 9 6 4 : V . M a l y s h k i n ( E d . ) , Para l l e l Compu t i n g Technologies. Proceedings. 1 99 5 . X I I , 497 pages. 1 99 5 . V o L 9 6 5 : H . Reichel (Ed.), Fun damentals of Computation Theory. Proceedi ngs, 1 99 5 . IX, 433 pages. 1 995.

VoL 966: PAR '95

S . Haridi, K . Ali, 1'. Magnusson (Eds.), EURO­ Parallel

734 J'•l!'CS. 1 99 5 .

Pmce<
1 99 5 . XV,

Vol %7: J . P . Bowen, M G Hinchey (Eds.). ZUM ' 9 5 The Z Formal Specificati
V o l . 9 6 8 : N . Dershow i t z, N . Lindenstrauss (Eds . ) , Conditional and Typed Rewriting Systems. Proceedings, 1 994. VIII, 375 pages. 1 99 5 . VoL 969: J . Wiedermann, P. Hoje k (Eds.), Mathematical

Foundations of Computer S c , �nce 1 99 5 . Proceedings, 1 995 XIIJ, 588 pages. l ""S

Sara (Ells ). Computer AMly<>< Pattern s Pmceedings, 1 995 . XV!ll, 960

Vol 970· V. Hlavac. R

Images and pages. 1 99 5 .

of

Expert Systems Applications Proceedings, 1 99 5 . X V , 654 pages. 1 99 5 .

V o L 97 1 : E . T . Schubert,

f' J

Windley, J . Alves-Foss

Proceedi ngs, 1 99 5 . X I I , Vol

S 9 8 pilges.

9 8 0 : A . Fen e i 1· " · J

1 99 5 .

R o l i m ( E d s . ) . P a ro l l e l

S l �<Jol
A lgor n h m ,l for fn e g u l a > l y

P 1 o <:ee d1 ngs, ! 99 5 . I X . 4 0<3 VQL

98 1 :

I . Wachsmuth, C - R . B o l l i nger, W . Brauer

( E d s . ). K I - 9 5 : A d v a n c es '" A r t i fi c i a l Intel l i g e n c e . Proceedings, 1 99 5 . X I I , 269 pages. (Subseries L N A I ) . V o l . 9 8 2 : S . D o a i t s e S w i ers tra, M . Herme n e g i l d o (Ed s . ) , Programming L a n g u a ge s : Implementat i o n s ,

L o g i c s and Programs . P rD c e e d i n g s , 1 9 9 5 . X I , 4 6 7 p a g: e s . 1 99 5 . Vol

983:

Pwceedings, VoL 984:

Advances

A.

M ycrDft

( E d ).

1 91)5 V l l l . 4 2 3 pages.

Static

1 995.

Analyd<

J . - M . Haton. M Keane, M . Manago (Eds . ) , in Case-Based Reasoning. Proceedings, 1 994.

V III, 307 pages. 1 99 5 .

V o l . 9 8 5 : T . S e l l i s ( E d . ) , Rules i n Database Systems. Proceedin g s , 1 99 5 . V I I I , 373 pages. 1 99 5 . V o l . 9 8 6 : Henry G . Baker

(Ed.), Memory

Management.

Proceedings, 1 99 5 . XII, 4 1 7 pages. 1 99 5 .

V o l . 98 7 : P . E . Camur&ti. H . Eveking ( E d s . ) , Correct H�1 d w a r e D e s i g n a" d Y e n fi c a t i o n M e t h D d < . P
V o l . 988:

A . U . Frank, W

Kuhn (Eds . ) , Spatial

Information T h e o r y . Proce e d i n g s , 1 9 9 5 . X l l l , 5 7 1

(Eds.), Higher Order Logic Theorem Proving and Its

pages. 1 99 5 .

Applications. Proceedings, 1 99 5 . Vlll, 400 pages. 1 99 5 .

V o l . 9 8 9 : W . S c h afer, P . B ot c l l a ( E ds . ) , Softw are

VoL 972: J . - M . Helary, M . Raynal ( E d s . ) , Distributed Algorithms. Proceedings,

1 995.

XI, 333 pages. 1 99 5 .

Engineering - ESEC ' 9 5 . Proceedi ngs, 1 99 5 . XII, 5 1 9 pages. 1 99 5 .

V o l . 990: C. P i n t o - ferreira, N . J . M amede ( Ed s . ) , Progress i n Artificial Intelligence. Proceedings, 1 99 5 . X I V , 4 8 7 p a g e s . 1 99 5 . (Subseries LNAI).

Vol. 1 0 1 2: M . Bartosek, J. Staudek, J . Wiedermann (Eds.),

SOPSEM

' 9 5 : T h e o r y and P r a c t i c e o f

Informatics. Proceedin g s , 1 99 5 . X I , 499 pages. 1 99 5 .

Vol. 99 1 : J . Wainer, A. Carvalho (Eds.), Advances in

V o l . 1 0 1 3 : T . W . L i n g , A . O . Mendelzon, L . Viei l l e

Artificial Intelligence. Proceedings, 1 99 5 . XII, 342

( E d s . ) , Deductive and Object-Oriented Databas e s .

pages. 1 995. (Subseries LNAI).

Proceedi ngs, 1 99 5 . X I V , 5 5 7 pages. 1 9 9 5 .

Vol. 992: M. Gori, G . Soda (Eds.), Topics i n Artificial Intelligence. Proceedings, 1 99 5 . XII, 45 1 pages. 1 99 5 .

Vol.

1 0 1 4 : A . P . d e l Pob i l , M . A . S e r n a , S p a t i a l

Representation a n d Motion Planning. X I I , 2 4 2 pages.

(Subseries LNAI).

1 99 5 .

Vol. 993 : T.C. Fogarty (Ed.), Evolutionary Computing.

V o l . 1 0 1 5 : B . B lumenthal, J . Gornostaev, C. Unger

Proceedings, 1 99 5 . VIII, 264 pages. 1 99 5 .

( Ed s . ), Human-Computer Interaction. Proceedi n g s ,

Vol. 9 9 4 : M . Hebert, J . Ponce, T. B o u l t , A. Gross (Eds.),

1 99 5 . VIII, 2 0 3 pages. 1 995.

O bj e c t

VOL. 1016: R. Cipolla, Active Visual Inference of Surface

Representation

in

C o m p u ter

Vision.

Proceedings, 1 994. VIII, 3 5 9 pages. 1 99 5 .

Shape. XII, 1 94 pages. 1 995.

Vol. 9 9 5 : S . M . Miiller, W . J . P a u l , The Complexity of

V o l . 1 0 1 7 : M . Nag! (Ed.), Graph-Theoretic Concepts

Simple Computer Architectures. X I I , 270 pages. 1 99 5 .

i n Computer Science. Proceedings, 1 995. XI, 406 pages.

V o l . 996: P . Dybjer, B . Nordstrom, J . Smith (Eds.).

1 99 5 .

Types for Proofs and Programs. Proceedings, 1 994. X ,

Vol. 1 0 1 8 : T.D.C. Little, R. Gusella (Eds.), Network a n d

202 pages. 1 995.

Operating Systems Support for Digital Audio a n d Video.

V o l . 9 9 7 : K . P . Jantke, T . Shinohara, T . Zeugmann

Proceedings, 1995. XI, 357 pages. 1 995.

( E d s . ) , Algorithmic Learning Theory. Proceedings,

Vol. 1 0 1 9 : E. Brinksma, W . R . Cleaveland, K.G. Larsen,

1 995. XV, 3 1 9 pages. 1 99 5 .

T . Margaria, B. Steffen (Eds . ) , Tools and Algorithms

V o l . 9 9 8 : A . C l arke, M . Campolargo, N . Karatzas

for the Construction and Analysis o f Systems. Selected

(Eds.), Bringing Telecommunication Services to the

Papers, 1 995. VII, 291 pages. 1 99 5 .

People - IS&N • 95. Proceedings, 1 99 5 . XII, 5 1 0 pages.

V o l . 1020: J.D. Watson (Ed.), Progress i n Case-Based

1 99 5 .

Reasoning. Proceedings, 1995. VIII, 209 pages. 1 995.

V o l . 9 9 9 : P. Antsaklis, W . Kohn, A. Nerode, S . Sastry

(Subseries LNAI).

(Eds.), Hybrid Systems II. VIII, 569 pages. 1 99 5 .

Vol. 1 02 1 : M.P. Papazoglou (Ed.), OOER '95: Object­

V o l . 1 000: J. v a n Leeuwen ( E d . ) , Computer Science

Oriented and Entity-Relationship Modeling. Proceedings.

Today. XIV, 643 pages. 1 99 5 .

1 99 5 . XVII, 45 1 pages. 1 995.

V o l . I 00 1 : M . Sudan, Efficient Checking of Polynomials

Vol. 1 022: P . H . Hartel, R . Plasmeijer (Eds.), Functional

and Proofs and the Hardness of Approximation Problems.

Programming Languages in Education. Proceedings, 1995.

XIV, 87 pages. 1 995.

X , 309 pages. 1995.

Vol. 1 00 2 : J.J. Kistler. Disconnected Operation i n a

Vol. 1023: K. Kanchanasut, J.-J. Levy (Eds.), Algorithms,

Distributed Pile System. X I X , 249 pages. 1 99 5 . V O L . 1 0 0 3 : P. Pandurang Nayak, Automated Modeling of Physical Systems. XXI, 232 pages. 1 995. (Subseries LNAI). Vol. 1 004: J. Staples, P. Eades, N . Katoh, A . Moffat ( Ed s .) , Algorithms a n d Computation. Proceed i n g s ,

Concurrency and Knowlwdge. Proceedings, 1 995. X, 4 10 pages. 1 995. Vol. 1 024: R.T. Chin, H . H . S . lp, A.C. Naiman, T.-C. Pong ( E d s . ) , Image Analysis Applications and Computer Graphics. Proceedings, 1 995. XVI, 5 3 3 pages. 1 99 5 . Vol. 1025: C . Boyd (Ed.), Cryptography and Coding.

1 99 5 . X V , 440 pages. 1 99 5 .

Proceedings, 1 995. IX, 2 9 1 pages. 1 995.

V o l . 1 00 5 : J . Estublier ( E d . ) , Software Configuration

V o L 1 02 6 : P.S. Thiagarajan ( E d . ) , Foundations o f

Management. Proceedings, 1 99 5 . IX, 3 1 1 pages. 1 995. V o l . 1 006: S. Bhalla ( E d . ) , Information Systems and

Software Technology a n d Theoretical Computer Science. Proceedings, 1995. XII, 5 1 5 pages. 1 995.

Data Management. Proceedings, 1 995. IX, 321 pages.

V o l . 1 02 7 : F . J . Brandenburg ( E d . ) , Graph Drawing.

1 995.

Proceedings, 1995. XII, 526 pages. 1 996.

V o l . 1 00 7 : A. B osselaers, B. Preneel (Eds.), Integrity

V o l . 1 02 8 : N . R . Adam, Y . Yesha (Eds.), Electronic

Primitives for Secure Information Systems. VII, 239

Commerce. X, 155 pages. 1 996.

pages. 1 99 5 .

VoL 1029: E . Dawson, J . Golic (Eds.), Cryptography:

V o l . 1 008: B . Prenee1 ( E d . ) , P a s t Software Encryption.

Policy and Algorithms. Proceedings, 1 995. XI, 327 pages.

Proceedings, 1 994. VIII, 367 pages. 1 99 5 .

1 996.

V o l . 1 009: M . B r o y , S . Hihnichen ( E d s . ) , KORSO:

Vol. 1 030: F. Pichler, R. Moreno-Dfaz, R. Albrecht (Eds.),

Methods, Languages, and Tools for the Construction

Computer Aided Systems Theory - EUROCAST ' 9 5 .

of Correct Software. X, 449 pages. 1 995. Vol.

Proceedings, ! 995. Xll, 539 pages. 1 996.

V o l . 1 0 1 0 : M . Veloso, A . Aamodt (Eds.), Case-Based Reasoning Research and Development. Proceedings,

V o L I 03 1 :

M.

T o u s s ai n t

(Ed.),

Ada

in

Europe.

Proceedings, 1995. XI, 455 pages. 1 996.

1 99 5 . X, 576 pages. 1 99 5 . (Subseries LNAI).

Vol. I 032: P. Godefroid, Partial-Order Methods for the

Vol. 1 0 1 1 : T . Furuhashi ( E d . ) , Advances i n Fuzzy

Verification of Concurrent Systems. IV, 143 pages. 1996.

Logic, Neural Networks and Genetic Algorithms. Pro­ ceedings, 1 994.

(Subseries LNAI).