## Maya Leshkowitz

## Abstract of Master Thesis (Weizmann Inst., 2017)

### On Randomness Complexity and Round Complexity in Interactive Proofs

Consider an interactive proof system for some set $S$ that has randomness
complexity $r(n)$ for instances of length $n$, and arbitrary round
complexity. We show a public-coin interactive proof system for $S$ of
round complexity $O(r(n)/\log n)$. That is, the resulting interactive proof
system is of the public-coin type even if the original was not.
Furthermore, the randomness complexity is preserved up to a constant factor,
and the resulting interactive proof system has perfect completeness.

In addition, we consider a natural alternative to the known public-coin
emulation of interactive proof systems proposed by Goldwasser and Sipser.
In the known emulation, the possible messages are essentially clustered
according to the probability that they are selected in the original
protocol, and the emulation selects a message at random among those that
belong to the heaviest cluster. In our alternative emulation, each cluster
is selected with probability that is proportional to its weight, and a
message is picked at random from this cluster. The crux of our work is
showing that, essentially, no matter how the prover behaves, it cannot
increase the probability that a message is selected by more than a constant
factor in compared to the original protocol. We also show that such a
constant loss is inevitable.

*Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, March 2017.*

Available: the thesis (in PDF file).

Back to Oded Goldreich's homepage.