## Or Meir

## 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.