[Colloquium] UC Theory Seminar - Roei Tell, Tuesday, January 3, 2023

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Roei Tell, PhD
Institute for Advanced Study and Center for Discreet Mathematics and Theoretical Computer Science



[Roei Tell headshot]

Tuesday, January 3, 2023 at 3:30pm
Kent Chemical Laboratory, Room 102


TITLE:   A free lunch theorem for de-randomization of proof systems, and consequences

ABSTRACT:  In the first half of the talk,  I'll set up some background, by describing two recent directions in the study of de-randomization: A non-black-box algorithmic framework, which replaces the classical PRG-based paradigm; and free lunch results, which eliminate randomness with essentially no runtime overhead.

In the second half we'll see one result along these directions: Under hardness assumptions, every doubly efficient proof system with constantly many rounds of interaction can be simulated by a deterministic NP-type verifier, with essentially no runtime overhead, such that no efficient adversary can mislead the deterministic verifier. Consequences include an NP-type verifier of this type for #SAT, running in time 2^{eps*n} for an arbitrarily small constant eps>0; and a complexity-theoretic analysis of the Fiat-Shamir heuristic in cryptography.

The talk is based on a joint work with Lijie Chen (UC Berkeley).

 Bio:  I’m a postdoc at IAS+DIMACS working in Theoretical Computer Science and Complexity Theory. Previously he was a postdoc at MIT and completed his PhD at the Weizmann Institute of Science.









HOST: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221230/73fae863/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 26387 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221230/73fae863/attachment-0001.jpg>