between the verifier and the prover to
m-rounds and this is not allowed (by
our definitions, which were crucial
to the complementary lemma). A less
natural, and somewhat optimistic, approach would be to repeat the random
coin tosses 2IP verifier m times, collect all the questions that it would like
to ask, say, the first prover and send
them together in one batch (and similarly with the second prover). Analysis
of such parallel repetition of 2IP verifiers was known to be a nontrivial
problem, 16, 32 yet even such an analysis
would only solve the first of the problems with the “naive” approach to error-reduction. The second problem is
that the transformation does not keep
the size of the transformed instance
linear in size and this turns out to be
a fatal. Dinur manages to overcome
this barrier by borrowing ideas from
“recycling” of randomness, 10, 23 which
suggests approaches for saving on this
blowup of the instance size. Analyzing
these approaches is nontrivial, but
Dinur manages to do so, with a relatively clean (and even reasonably
short) proof. The reader is pointed to
the original paper12 for full details,
and to a more detailed survey31 for information on the context.
conclusion
The goal of this article is to mainly
highlight the notion of a PCP, and its
utility in computational complexity.
Due to limitations on space and time,
we were barely able to scratch the surface. In particular we did not focus on
the explicit parameters and the tightest
results known. The literature on PCPs
is rich with a diversity of parameters,
but we chose to focus on only two: the
query complexity and the gap. The
trade-off between the two is already interesting to study and we mention one
tight version, which is extremely useful
in “inapproximability” results. Håstad22
shows that the query complexity in the
PCP theorem can be reduced to 3 bits,
while achieving a gap arbitrarily close
to 1/2. So a verifier confronted with a
fallacious assertion can read just 3 bits
of the proof, and would find an error
with probability (almost) one-half!
One of the somewhat strange aspects
of PCP research has been that even
though the existence of PCPs seems to
be a “positive” statement (verification
can be very efficient), its use is mostly
negative (to rule out approximation algorithms). One may wonder why the
positive aspect has not found a use. We
suggest that positive uses might emerge
as more and more of our life turns digital, and we start worrying not only about
the integrity of the data, but some of the
properties they satisfy, that is, we may
not only wish to store some sequence of
bits x, but also preserve the information
that P(x) = y for some program P that
took x as an input.
One barrier to such uses is the current size of PCPs. PCP proofs, even
though they are only polynomially larger than classical proofs; they are much
larger, and this can be a prohibitive cost
in practice. The good news is that this
parameter is also improving. An optimistic estimate of the size of the PCP
proof in the work of Håstad22 might be
around n10 , where n is the size of the
6
classical proof! But recent results have
improved this dramatically since and
current best proofs9, 12 work with PCPs
of size around O(n(log n)O( 1)) (so the constant in the exponent has dropped from
106 to 1 + o( 1)). Thus far, this reduction in PCP size has come at the price
of increased query complexity, but this
concern is being looked into by current
research and so a positive use of PCPs
may well be seen in the near future.
acknowledgments
I would like to thank the anonymous
reviewers for their valuable comments,
and for detecting (mathematical!) errors in the earlier version of this manuscript (despite the fact that this article
is not written in the PCP format).
References
1. arora, s., Babai, l., stern, J., sweedyk, Z. the hardness
of approximate optima in lattices, codes and systems
of linear equations. J. Comput. Syst. Sci. 54, 2 (apr.
1997), 317–331.
2. arora, s., lund, c. hardness of approximations.
Approximation Algorithms for NP-Hard Problems.
d.s. hochbaum, ed. PWs, 1995.
3. arora, s., lund, c., motwani, r., sudan, m., szegedy, m.
Proof verification and the hardness of approximation
problems. J. ACM 45, 3 (may 1998), 501–555.
4. arora, s., safra, s. Probabilistic checking of proofs: a new
characterization of nP. J. ACM 45, 1 (Jan. 1998), 70–122.
5. Babai, l., fortnow, l., levin, l.a., szegedy, m. checking
computations in polylogarithmic time. in Proceedings
of the 23rd ACM Symposium on the Theory of
Computing (new york, 1991), acm, 21–32.
6. Babai, l., fortnow, l., lund, c. non-deterministic
exponential time has two-prover interactive protocols.
Comput. Complexity 1, 1 (1991), 3–40.
7. Babai, l., moran, s. arthur-merlin games: a
randomized proof system, and a hierarchy of
complexity class. J. Comput. Syst. Sci. 36, 2 (apr.
1988), 254–276.
8. Ben-or, m., goldwasser, s., kilian, J., Wigderson,
a. multi-prover interactive proofs: how to remove
intractability. in Proceedings of the 20th Annual
ACM Symposium on the Theory of Computing (1988),
113–131.
9. Ben-sasson, e., sudan, m. short PcPs with poly-log
rate and query complexity. in Proceedings of the 37th
Annual ACM Symposium on Theory of Computing
(new york, 2005), acm, 266–275.
10. cohen, a., Wigderson, a. dispersers, deterministic
amplification, and weak random sources (extended
abstract). in IEEE Symposium on Foundations of
Computer Science (1989), 14–19.
11. cook, s.a. the complexity of theorem-proving
procedures. in Proceedings of the 3rd ACM
Symposium Theory of Computing (ohio, 1971), shaker
heights, 151–158.
12. dinur, i. the PcP theorem by gap amplification. in
Proceedings of the 38th Annual ACM Symposium on
Theory of Computing (new york, 2006), acm, 241–250.
Preliminary version appeared as an eccc technical
report tr05-046.
13. dinur, i., reingold, o. assignment testers: towards
a combinatorial proof of the PcP-theorem. in
Proceedings of the 45th Annual IEEE Symposium on
Foundations of Computer Science (loc alamitos, ca,
usa, 2004), ieee, 155–164.
14. feige, u. a threshold of ln n for approximating set
cover. J. ACM 45, 4 (1998), 634–652.
15. feige, u., goldwasser, s., lovász, l., safra,
s., szegedy, m. interactive proofs and the hardness
of approximating cliques. J. ACM 43, 2 (1996),
268–292.
16. fortnow, l., rompel, J., sipser, m. on the power of
multi-prover interactive protocols. Theor. Comput. Sci.
134, 2 (1994), 545–557.
17. garey, m.a., Johnson, d.s. Computers and
Intractability. freeman, 1979.
18. goldreich, o. Modern Cryptography, Probabilistic Proofs
and Pseudorandomness, volume 17 of Algorithms and
Combinatorics. springer-Verlag, 1998.
19. goldreich, o., micali, s., Wigderson, a. Proofs that yield
nothing but their validity or all languages in nP have
zero-knowledge proof systems. J. ACM 38, 1 (July 1991),
691–729. Preliminary version in IEEE FOCS, 1986.
20. goldwasser, s., micali, s., rackoff, c. the knowledge
complexity of interactive proof systems. SIAM J.
Comput. 18, 1 (february 1989), 186–208.
21. håstad, J. clique is hard to approximate within n to
the power 1-epsilon. Acta Mathemat. 182 (1999),
105–142.
22. håstad, J. some optimal inapproximability results.
J. ACM 48 (2001),798–859.
23. impagliazzo, r., Zuckerman, d. how to recycle random
bits. in IEEE Symposium on Foundations of Computer
Science (1989), 248–253.
24. karloff, h., Zwick, u. a 7/8-approximation algorithm
for max 3sat? in FOCS ’97: Proceedings of the 38th
Annual Symposium on Foundations of Computer
Science (FOCS ’ 97) (Washington, dc, usa, 1997), ieee
computer society, 406–415.
25. karp, r.m. reducibility among combinatorial problems.
Complexity of Computer Computations. r. miller, and
J. thatcher, eds.1972, 85–103.
26. khot, s. guest column: inapproximability results via long
code based pcps. SIGACT News 36, 2, 25–42, 2005.
27. levin, l.a. universal search problems. Problemy
Peredachi Informatsii, 9, 3 (1973), 265–266.
28. lund, c., fortnow, l., karloff, h. J., nisan, n. algebraic
methods for interactive proof systems. J. ACM 39, 4
(oct. 1992), 859–868.
29. lund, c., yannakakis, m. on the hardness of
approximating minimization problems. J. ACM 41, 5
(sept. 1994), 960–981.
30. Papadimitriou, c., yannakakis, m. optimization,
approximation, and complexity classes. J. Comput.
Syst. Sci. 43 (1991), 425–440.
31. radhakrishnan, J., sudan, m. on dinur’s proof of the
PcP theorem. Bulletin (New Series) Amer. Math. Soc.,
44, 1 (Jan. 2007), 19–61.
32. raz, r. a parallel repetition theorem. SIAM J. Comput.
27, 3 (1998), 763–803.
33. shamir, a. iP = PsPace. J. ACM 39, 4 (oct. 1992),
869–877.
34. shannon, c.e. a mathematical theory of communication.
Bell Syst. Tech. J. 27, (1948), 379–423, 623–656.
Madhu Sudan is fujitsu Professor of eecs at mit's
computer science and artificial intelligence laboratory,
cambridge, ma.
© 2009 acm 0001-0782/09/0300 $5.00
