How NP got a new definition: a survey of probabilistically checkable proofs
---
paper_title: Alternation in interaction

paper_content:

We study competing-prover one-round interactive proof systems. We show that one-round proof systems in which the first prover is trying to convince a verifier to accept and the second prover is trying to make the verifier reject recognized languages in NEXPTIME, and, with restrictions on communication and randomness, languages in NP. We extended the restricted model to an alternating sequence of k competing provers, which we show characterizes /spl Sigmasub k-1sup P/. Alternating oracle proof systems are also examined. >
---
paper_title: Random debaters and the hardness of approximating stochastic functions

paper_content:

A random probabilistically checkable debate system (RPCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who aims to prove that the input x is in L, and Player 0, who selects a move uniformly at random from the set of legal moves. This model is a natural restriction of the PCDS model (Condon et al., Proc. 25th ACM Symposium on Theory of Computing, p.304-15, 1993,). We show that L has an RPCDS in which the verifier flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE. Using this new characterization of PSPACE, we show that certain stochastic PSPACE-hard functions are as hard to approximate closely as they are to compute exactly. Examples include optimization versions of dynamic graph reliability, stochastic satisfiability, Mah-Jongg, stochastic coloring, stochastic generalized geography, and other "games against nature". >
---
paper_title: Probabilistic checking of proofs: a new characterization of NP

paper_content:

We give a new characterization of NP: the class NP contains exactly those languages <italic>L</italic> for which membership proofs (a proof that an input <italic>x</italic> is in <italic>L</italic>) can be verified probabilistically in polynomial time using <italic>logarithmic</italic> number of random bits and by reading <italic>sublogarithmic</italic> number of bits from the proof. ::: We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
---
paper_title: Some optimal inapproximability results

paper_content:

We prove optimal, up to an arbitrary e > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
---
paper_title: A 7/8-approximation algorithm for MAX 3SAT?

paper_content:

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.
---
paper_title: Optimization, approximation, and complexity classes

paper_content:

We define a natural variant of NP, MAX NP , and also a subclass called MAX SNP . These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transformation (called L - reduction ) that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme iff the whole class does. These results may help explain the lack of progress on the approximability of a host of optimization problems.
---
paper_title: Approximation Algorithms For NP-Hard Problems

paper_content:

This is the first book to fully address the study of approximation algorithms as a tool for coping with intractable problems. With chapters contributed by leading researchers in the field, this book introduces unifying techniques in the analysis of approximation algorithms. APPROXIMATION ALGORITHMS FOR NP-HARD PROBLEMS is intended for computer scientists and operations researchers interested in specific algorithm implementations, as well as design tools for algorithms. Among the techniques discussed: the use of linear programming, primal-dual techniques in worst-case analysis, semidefinite programming, computational geometry techniques, randomized algorithms, average-case analysis, probabilistically checkable proofs and inapproximability, and the Markov Chain Monte Carlo method. The text includes a variety of pedagogical features: definitions, exercises, open problems, glossary of problems, index, and notes on how best to use the book.
---
paper_title: Algebraic methods for interactive proof systems

paper_content:

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].
---
paper_title: Designing programs that check their work

paper_content:

A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class FP of functions computable in polynomial time. Problems in FP for which checkers are presented in this paper include Sorting, Matrix Rank and GCD. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Two structural theorems are proven here. One is a characterization of problems that can be checked. The other theorem establishes equivalence classes of problems such that whenever one problem in a class is checkable, all problems in the class are checkable.
---
paper_title: Hiding instances in multioracle queries

paper_content:

Abadi, Feigenbaum, and Kilian have considered instance-hiding schemes [1]. Let f be a function for which no randomized polynomial-time algorithm is known; randomized polynomial-time machine A wants to query an oracle B for f to obtain f(x), without telling B exactly what x is. It is shown in [1] that, if f is an NP-hard function, A cannot query a single oracle B while hiding all but the size of the instance, assuming that the polynomial hierarchy does not collapse. This negative result holds for all oracles B, including those that are non-r.e.
---
paper_title: Trading group theory for randomness

paper_content:

In a previous paper [BS] we proved, using the elements of the theory of nilpotent groups , that some of the fundamental computational problems in matriz groups belong to NP . These problems were also shown to belong to coNP , assuming an unproven hypothesis concerning finite simple groups . The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments. The result we prove is that relative to a random oracle B , the mentioned matrix group problems belong to ( NP∩coNP ) B . The problems we consider are membership in and order of a matrix group given by a list of generators. These problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. Hence NP∩coNP might be the lowest natural complexity class they may fit in. We remark that the results remain valid for black box groups where group operations are performed by an oracle. The tools we introduce seem interesting in their own right. We define a new hierarchy of complexity classes AM ( k ) “just above NP ”, introducing Arthur vs. Merlin games , the bounded-away version of Papdimitriou's Games against Nature . We prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to AM=AM (2). Using a combinatorial lemma on finite groups [BE], we construct a game by which the nondeterministic player (Merlin) is able to convince the random player (Arthur) about the relation [ G ]= N provided Arthur trusts conclusions based on statistical evidence (such as a Slowly-Strassen type “proof” of primality). One can prove that AM consists precisely of those languages which belong to NP B for almost every oracle B . Our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the User vs. Expert games of Goldwasser, Micali and Rackoff.
---
paper_title: Probabilistic checking of proofs: a new characterization of NP

paper_content:

We give a new characterization of NP: the class NP contains exactly those languages <italic>L</italic> for which membership proofs (a proof that an input <italic>x</italic> is in <italic>L</italic>) can be verified probabilistically in polynomial time using <italic>logarithmic</italic> number of random bits and by reading <italic>sublogarithmic</italic> number of bits from the proof. ::: We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
---
paper_title: Transparent Proofs and Limits to Approximation

paper_content:

We survey a major collective accomplishment of the theoretical computer science community on efficiently verifiable proofs.
---
paper_title: Lectures on proof verification and approximation algorithms

paper_content:

Thank you for downloading lectures on proof verification and approximation algorithms. As you may know, people have look hundreds times for their favorite readings like this lectures on proof verification and approximation algorithms, but end up in harmful downloads. Rather than reading a good book with a cup of tea in the afternoon, instead they are facing with some harmful virus inside their laptop.
---
paper_title: Interactive proofs and the hardness of approximating cliques

paper_content:

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.
---
paper_title: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols

paper_content:

We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:
---
paper_title: On the Power of Multi-Prover Interactive Protocols

paper_content:

Abstract We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.
---
paper_title: Some optimal inapproximability results

paper_content:

We prove optimal, up to an arbitrary e > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
---
paper_title: Interactive proofs and the hardness of approximating cliques

paper_content:

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.
---
paper_title: Two-Prover Protocols---Low Error at Affordable Rates

paper_content:

We introduce the miss-match form for two-prover one-round proof systems. Any two-prover one-round proof system can be easily modified so as to be in miss-match form. Proof systems in miss-match form have the "projection" property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. ::: Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to $\epsilon$. This upper bound depends only on p and on $\epsilon$ (polynomial in 1/(1-p) and in $1/\epsilon$). Based on previous work, it follows that for any $\epsilon >0,$ NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most $\epsilon$. ::: As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.
---
paper_title: Improved non-approximability results

paper_content:

We indicate strong non-approximability factors for central problems: N{sup 1/4} for Max Clique; N{sup 1/10} for Chromatic Number; and 66/65 for Max 3SAT. Underlying the Max Clique result is a proof system in which the verifier examines only three {open_quotes}free bits{close_quotes} to attain an error of 1/2. Underlying the Chromatic Number result is a reduction from Max Clique which is more efficient than previous ones.
---
paper_title: Some optimal inapproximability results

paper_content:

We prove optimal, up to an arbitrary e > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
---
paper_title: Probabilistic checking of proofs: a new characterization of NP

paper_content:

We give a new characterization of NP: the class NP contains exactly those languages <italic>L</italic> for which membership proofs (a proof that an input <italic>x</italic> is in <italic>L</italic>) can be verified probabilistically in polynomial time using <italic>logarithmic</italic> number of random bits and by reading <italic>sublogarithmic</italic> number of bits from the proof. ::: We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
---
paper_title: Linearity testing in characteristic two

paper_content:

Let Dist(f,g)=Pr/sub u/[f(u)/spl ne/g(u)] denote the relative distance between functions f,g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f,g). Given a function f:G/spl rarr/H we let Err(f)=Pr/sub u,/spl upsi//[f(u)+f(/spl upsi/)/spl ne/f(u+/spl upsi/)] denote the rejection probability of the Blum-Luby-Rubinfeld (1993) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in particular lower bounds on Err(f) in terms of Dist(f). We discuss when the underlying groups are G=GF(2)/sup n/ and H=GF(2). In this case, the collection of linear functions describe a Hadamard code of block length 2/sup n/ and for an arbitrary function f mapping GF(2)/sup n/ to GF(2) the distance Dist(l) measures its distance to a Hadamard code. Err(f) is a parameter that is "easy to measure" and linearity testing studies the relationship of this parameter to the distance of f. The code and corresponding test are used in the construction of efficient probabilistically checkable proofs and thence in the derivation of hardness of approximation. Improved analyses translate into better nonapproximability results. We present a description of the relationship between Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete in some. We present functions L,U:[0,1]/spl rarr/[0,1] such that for all x /spl isin/ [0,1] we have L(x)/spl les/Err(f)/spl les/U(x) whenever Dist(f)=x, with the upper bound being tight on the whole range, and the lower bound tight on a large part of the range and close on the rest. Part of our strengthening is obtained by showing a new connection between linearity testing and Fourier analysis.
---
paper_title: Some optimal inapproximability results

paper_content:

We prove optimal, up to an arbitrary e > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
---
paper_title: Self-testing polynomial functions efficiently and over rational domains

paper_content:

In this paper we give the first self-testers and checkers for polynomials over rational and integer domains. We also show significantly stronger bounds on the efficiency of a simple modification of the algorithm for self-testing polynomials over finite fields given in [8].
---
paper_title: Improved low-degree testing and its applications

paper_content:

NP = PCP(logn, 1) and related results crucially depend upon the close connection between the probability with which a function passes a low degree test and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan [30]. The strongest previously known connection for this test states that a function passes the test with probability δ for some δ > 7/8 iff the function has agreement ≈ δ with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small δ, provided the field size is polynomially larger than d/δ. The analysis uses a version of Hilbert irreducibility, a tool of algebraic geometry. As a consequence we obtain an alternate construction for the following proof system: A constant prover 1-round proof system for NP languages in which the verifier uses O(logn) random bits, receives answers of size O(logn) bits, and has an error probability of at most 2− log 1− . Such a proof system, which implies the NP-hardness of approximating Set Cover to within Ω(logn) factors, has already been obtained by Raz and Safra [29]. Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present. A second consequence of our analysis is a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field. If the program is correct only on δ fraction of inputs where δ = 1/ |F| 0.5, then the tester/corrector determines δ and generates O( 1 δ ) values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct O( 1 δ ) randomized programs such that one of them is correct on every input, with high probability. Such a strong selfcorrector is a useful tool in complexity theory with some applications known. ∗arora@cs.princeton.edu. Supported by an NSF CAREER award, an Alfred P. Sloan Fellowship, and a Packard Fellowship. †madhu@lcs.mit.edu. Laboratory for Computer Science, MIT, Cambridge, MA 02139. Part of this work was done when this author was at the IBM Thomas J. Watson Research Center.
---
paper_title: Probabilistic checking of proofs: a new characterization of NP

paper_content:

We give a new characterization of NP: the class NP contains exactly those languages <italic>L</italic> for which membership proofs (a proof that an input <italic>x</italic> is in <italic>L</italic>) can be verified probabilistically in polynomial time using <italic>logarithmic</italic> number of random bits and by reading <italic>sublogarithmic</italic> number of bits from the proof. ::: We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
---
paper_title: Interactive proofs and the hardness of approximating cliques

paper_content:

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.
---
paper_title: Extractors from Reed-Muller codes

paper_content:

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, researchers had failed to build extractors directly from a good code without using other tools from pseudorandomness. We succeed in constructing an extractor directly from a Reed-Muller code. To do this, we develop a novel proof technique. Furthermore, our construction is the first to achieve a degree close to linear. In contrast, the best previous constructions brought the log of the degree within a constant of optimal, which gives polynomial degree. This improvement is important for certain applications. For example, it follows that approximating the VC dimension to within a factor of N/sup 1-/spl delta// is AM-hard for any positive /spl delta/.
---
paper_title: How to go beyond the black-box simulation barrier

paper_content:

The simulation paradigm is central to cryptography. A simulator is an algorithm that tries to simulate the interaction of the adversary with an honest party, without knowing the private input of this honest party. Almost all known simulators use the adversary's algorithm as a black-box. We present the first constructions of non-black-box simulators. Using these new non-black-box techniques, we obtain several results that were previously proven to be impossible to obtain using black-box simulators. Specifically, assuming the existence of collision resistent hash functions, we construct a new zero-knowledge argument system for NP that satisfies the following properties: 1. This system has a constant number of rounds with negligible soundness error. 2. It remains zero knowledge even when composed concurrently n times, where n is the security parameter. Simultaneously obtaining 1 and 2 has been recently proven to be impossible to achieve using black-box simulators. 3. It is an Arthur-Merlin (public coins) protocol. Simultaneously obtaining 1 and 3 was known to be impossible to achieve with a black-box simulator. 4. It has a simulator that runs in strict polynomial time, rather than in expected polynomial time. All previously known constant-round, negligible-error zero-knowledge arguments utilized expected polynomial-time simulators.
---
paper_title: Alternation in interaction

paper_content:

We study competing-prover one-round interactive proof systems. We show that one-round proof systems in which the first prover is trying to convince a verifier to accept and the second prover is trying to make the verifier reject recognized languages in NEXPTIME, and, with restrictions on communication and randomness, languages in NP. We extended the restricted model to an alternating sequence of k competing provers, which we show characterizes /spl Sigmasub k-1sup P/. Alternating oracle proof systems are also examined. >
---
paper_title: Improved decoding of Reed-Solomon and algebraic-geometric codes

paper_content:

Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x/sub i/.y/sub i/)}/sub i=1//sup n/, x/sub i/,y/sub i//spl isin/F, and a degree parameter k and error parameter e, find all univariate polynomials p of degree at most k such that y/sub i/=p(x/sub i/) for all but at most e values of i/spl isin/{1....,n}. We give an algorithm that solves this problem for e 1/3, where the result yields the first asymptotic improvement in four decades. The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometric codes. In both cases, we obtain a list decoding algorithm that corrects up to n-/spl radic/(n-d-) errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometric codes extends the methods of Shokrollahi and Wasserman (1998) and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve fitting problem, which is of use in soft-decision decoding algorithms for Reed-Solomon codes.
---
paper_title: Random debaters and the hardness of approximating stochastic functions

paper_content:

A random probabilistically checkable debate system (RPCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who aims to prove that the input x is in L, and Player 0, who selects a move uniformly at random from the set of legal moves. This model is a natural restriction of the PCDS model (Condon et al., Proc. 25th ACM Symposium on Theory of Computing, p.304-15, 1993,). We show that L has an RPCDS in which the verifier flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE. Using this new characterization of PSPACE, we show that certain stochastic PSPACE-hard functions are as hard to approximate closely as they are to compute exactly. Examples include optimization versions of dynamic graph reliability, stochastic satisfiability, Mah-Jongg, stochastic coloring, stochastic generalized geography, and other "games against nature". >
---
paper_title: Pseudorandom generators without the XOR lemma

paper_content:

Summary form only given. R. Impagliazzo and A. Wigderson (1997) have recently shown that if there exists a decision problem solvable in time 2/sup O(n)/ and having circuit complexity 2/sup /spl Omega/(n)/ (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson (1994) generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.
---
paper_title: Improved Efficient Arguments

paper_content:

We consider complexity of perfect zero-knowledge arguments [4]. Let T denote the time needed to (deterministically) check a proof and let L denote an appropriate security parameter. We introduce new techniques for implementing very efficient zero-knowledge arguments. The resulting argument has the following features: ::: ::: ::: The arguer can, if provided with the proof that can be deterministically checked in O(T) time, run in time O(TL O(1)). The best previous bound was O(T 1+e L O(1)). ::: ::: ::: The protocol can be simulated in time O(L O(1)). The best previous bound was O(T 1+e L O(1)). ::: ::: ::: A communication complexity of O(L lg L), where L is the security parameter against the prover. The best previous known bound was O(L lg T).
---

Title: How NP Got a New Definition: A Survey of Probabilistically Checkable Proofs
Section 1: PCP theorems: an informal introduction
Description 1: This section introduces the PCP theorems with an example and explains their significance in proof verification.

Section 2: New definition of NP
Description 2: This section explores how the PCP theorems provide new definitions for the complexity class NP.

Section 3: Optimization, approximation, and PCP theorems
Description 3: This section discusses the impact of PCP theorems on optimization problems, approximation algorithms, and NP-hardness.

Section 4: History and context
Description 4: This section provides historical background and context on the development of PCPs.

Section 5: Definitions and results
Description 5: This section defines the PCP class, other PCP-like classes, and lists the main results.

Section 6: Proof of the PCP theorems
Description 6: This section outlines the key ideas and techniques used in proving the PCP theorems.

Section 7: Local tests for global properties
Description 7: This section describes probabilistic local checks that verify global properties of a provided certificate.

Section 8: Further applications of PCP techniques
Description 8: This section highlights notable applications of PCP techniques in various fields.