<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div style="-webkit-text-size-adjust: auto;">ATTENTION: THIS QUARTER THE SEMINAR WILL BE IN A DIFFERENT ROOM (BUT THE </div><div style="-webkit-text-size-adjust: auto;">SAME BUILDING)</div><span style="-webkit-text-size-adjust: auto;"><div><br></div>Departments of Mathematics & Computer Science</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Combinatorics & Theory Seminar</span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"><span dir="ltr">Tuesday, January 3, 3:30pm</span></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">Location Kent <b>102</b></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;"></span><br style="-webkit-text-size-adjust: auto;"><span style="-webkit-text-size-adjust: auto;">SPEAKER: </span><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);">Roei Tell (IAS)</span><div style="-webkit-text-size-adjust: auto;"><br><div>TITLE: A free lunch theorem for de-randomization of proof systems, and consequences<br><br>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.<div dir="ltr"></div></div><div><br></div><div>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.</div><div><br></div><div>The talk is based on a joint work with Lijie Chen (UC Berkeley).</div></div><div dir="ltr"></div></body></html>