<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Arial Rounded MT Bold";
panose-1:2 15 7 4 3 5 4 3 2 4;}
@font-face
{font-family:"Arial Black";
panose-1:2 11 10 4 2 1 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:14.0pt">Roei Tell, PhD</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Arial Rounded MT Bold",sans-serif;color:black">Institute for Advanced Study and Center for Discreet Mathematics and Theoretical Computer Science</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><img width="211" height="205" style="width:2.1979in;height:2.1354in" id="Picture_x0020_1" src="cid:image001.jpg@01D91090.8E57E400" alt="Roei Tell headshot"><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, </span>
</b><b><span style="font-size:11.0pt">January 3<span style="color:black">, 202</span>3<span style="color:black"> at 3:30pm</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Kent Chemical Laboratory, Room 102</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><br>
<b><i>TITLE: </i></b> </span><span style="font-size:14.0pt"> </span><b><span style="font-size:13.5pt;font-family:"Arial Black",sans-serif;color:black">A free lunch theorem for de-randomization of proof systems, and consequences</span></b><span style="font-size:14.0pt"><br>
</span><span style="font-size:11.0pt"><br>
<b><i>ABSTRACT:</i></b> </span><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><br>
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.<br>
<br>
The talk is based on a joint work with Lijie Chen (UC Berkeley). </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:13.5pt;font-family:"Arial Black",sans-serif;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> <b><i>Bio</i></b></span><b><i><span style="font-size:12.0pt">:</span></i></b><span style="font-size:12.0pt;color:black;background:white">
</span><span style="font-size:12.0pt;color:black">I’m </span><span style="font-size:12.0pt">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</span><span style="font-size:11.0pt">.</span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><br>
<br>
<br>
<br>
<br>
<br>
<br>
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt">HOST: </span></b><b><span style="font-size:14.0pt">Aaron Potechin</span></b><o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
</body>
</html>