Probabilistic proof systems is a paradigm of complexity theory, whose study evolves around questions such as Probabilistic proof systems is a paradigm of complexity theory that evolves around questions such as "how can we use randomness to prove and verify assertions?", "what do we gain from using randomness in verification procedures?", and "what assertions can be verified by probabilistic verification procedures?". The study of those questions has began in the 1980's, and led to several of the most important achievements of complexity theory since then.
Many of the key results regarding probabilistic proof systems rely on sophisticated algebraic techniques. While those algebraic techniques are very important and useful, they seem to give little intuition as to why those results hold. Given this state of affairs, it is an important goal to gain a better understanding of those results and the reasons for which they hold. In her seminal paper, Dinur (J. ACM 54(3)) has made a big step toward achieving this goal by giving an alternative proof of one of the key results in this area, namely the PCP theorem, using a combinatorial approach. Her proof is not only considerably simpler than the original proof, but also seems to shed more light on the intuitions that underlie the theorem.
In this thesis, we pursue this direction further, by providing alternative proofs for several key results about probabilistic proof systems. Our alternative proofs do not use algebra (or use almost no algebra), and are more intuitive, in our opinion. In particular:
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, June 2011.
Available: the thesis (in PDF).
Back to Oded Goldreich's homepage.