## Abstract of PhD Thesis (Weizmann Inst., 2011)

### Title: Combinatorial Constructions of Probabilistic Proof Systems

Available: the thesis (in PDF).

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:

• We show that it is possible to prove that IP=PSPACE using general error correcting codes and their tensor products, instead of low degree polynomials.
• We provide a combinatorial construction of PCPs with verifiers that are as efficient as those obtained by the algebraic methods.
• We provide an (almost) combinatorial construction of PCPs of length n (log n)^O(loglog n), coming very close to the state of the art obtained by algebraic constructions (whose proof length is n(log n)^O(1) ).
• We provide a combinatorial construction of PCPs with sub-constant soundness error that match the state of the art obtained by algebraic constructions, and along the way develop a technique of derandomized parallel repetition.

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.