Search Mailing List Archives
[theory-seminar] Omer speaking at theory seminar thursday
Gregory Valiant
gvaliant at cs.stanford.edu
Wed Apr 13 23:42:06 PDT 2016
Hi Friends,
Just a reminder that Omer will be giving the theory will be giving the
theory seminar tomorrow (Thursday) at 4:15.
See you there,
-greg
On Mon, Apr 11, 2016 at 1:02 PM, Gregory Valiant
<gvaliant at cs.stanford.edu> wrote:
> 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
More information about the theory-seminar
mailing list