[theory-seminar] Omer speaking at theory seminar thursday

[Gregory Valiant]

Hi Friends,
Omer will be speaking at the theory seminar this coming Thursday, 4:15
in Gates 463a.  More info below.

Hope to see you all there,
-g

Speaker: Omer Reingold (Stanford)
Date/time/location: Thursday 4/14, 4:15pm Gates 463a
Title: Constant-round Interactive-proofs for Delegating Computation
Abstract:
Interactive proofs, introduced by Goldwasser, Micali and Rackoff, have
had a dramatic impact on Complexity Theory and Cryptography. In
particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows
an all-powerful but untrusted prover to convince a polynomial-time
verifier of the validity of extremely complicated statements (as long
as they can be evaluated using polynomial space). The interactive
proof system designed for this purpose requires a large number of
communication rounds and heavy computation for generating the proof.

We introduce new interactive proofs that are very efficient in the
number of rounds and computation time, that are particularly well
suited for delegating bounded-space computations (e.g., in the context
of cloud computing). Our main result is that for every statement that
can be evaluated in polynomial time and bounded-polynomial space there
exists an interactive proof that satisfies the following strict
efficiency requirements:

(1) the honest prover runs in polynomial time, (2) the verifier is
almost linear time (and under some conditions

even sub linear), and (3) the interaction consists of only a constant
number of communication rounds.  Prior to this work, very little was
known about the power of efficient, constant-round interactive proofs.

Joint work with Guy Rothblum and Ron Rothblum