Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Omer speaking at theory seminar thursday

Gregory Valiant gvaliant at
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,

On Mon, Apr 11, 2016 at 1:02 PM, Gregory Valiant
<gvaliant at> 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