[Theory] UC Theory Seminar
Alexander Razborov
razborov at uchicago.edu
Tue Dec 27 15:31:34 CST 2022
ATTENTION: THIS QUARTER THE SEMINAR WILL BE IN A DIFFERENT ROOM (BUT THE
SAME BUILDING)
Happy New Year to everyone.
Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar
Tuesday, January 3, 3:30pm
Location Kent 102
SPEAKER: Roei Tell (IAS)
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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221227/4495021e/attachment.html>
More information about the Theory
mailing list