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 cs.stanford.edu
Thu Apr 14 16:00:53 PDT 2016


Theory seminar in 15 minutes!

On Wed, Apr 13, 2016 at 11:42 PM, Gregory Valiant
<gvaliant at cs.stanford.edu> wrote:
> 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