<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">REMINDER:</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><br class=""></font></b></div><div class=""><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Department of Mathematics & Computer Science</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Combinatorics & Theory Seminar</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><br class=""></font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Tuesday, December 3, 2019</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Ryerson 251@ 3:30 pm</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class=""> </font></b></div><div class=""><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Lijie Chen</font></b></div><div class=""><b class=""><font face="TimesNewRomanPSMT" size="4" class="">MIT</font></b></div><div class=""><b class=""><span style="font-size: 16pt; font-family: "Times New Roman", serif;" class=""><a href="http://www.mit.edu/lijieche/" class="">http://www.mit.edu/lijieche/</a></span></b></div><div class=""><b class=""><p class="MsoNormal" align="center" style="text-align: center;"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class=""><o:p class=""> </o:p></span></p><p class="MsoNormal" align="center" style="text-align: center;"><span style="font-family: "Times New Roman", serif; font-size: 14pt;" class="">Title: “Strong Average-Case Lower Bounds from Non-trivial Derandomization”</span></p><p class="MsoNormal"><span style="font-family: "Times New Roman", serif; font-size: 14pt;" class="">Abstract:</span><span style="font-family: "Times New Roman", serif; font-size: 14pt;" class=""> We prove that for all constants a, NQP = NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 circuits. Previously, it was even open whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2] circuits. As a straightforward application, we obtain an infinitely often non-deterministic pseudorandom generator for poly-size ACC^0 circuits with seed length 2^{log^eps n}, for all eps > 0. More generally, we establish a connection showing that, for a typical circuit class C, non-trivial nondeterministic CAPP algorithms imply strong (1/2 + 1/n^{omega(1)}) average-case lower bounds for nondeterministic time classes against C circuits. The existence of such (deterministic) algorithms is much weaker than the widely believed conjecture PromiseBPP = PromiseP. Our new results build on a line of recent works, including [Murray and Williams, STOC 2018], [Chen and Williams, CCC 2019], and [Chen, FOCS 2019]. In particular, it strengthens the corresponding (1/2 + 1/polylog(n))-inapproximability average-case lower bounds in [Chen, FOCS 2019]. The two important technical ingredients are techniques from Cryptography in NC^0 [Applebaum et al., SICOMP 2006], and Probabilistic Checkable Proofs of Proximity with NC^1-computable proofs. This is joint work with Hanlin Ren from Tsinghua University.</span></p><p class="MsoNormal"><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: justify;" class="">Host: Prof. Andrew Drucker</span></p><p class="MsoNormal"><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: center;" class="">(Refreshments will be served prior to the talk at 3:15 pm in Ry. 257)</span></p><div class=""><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: center;" class=""><br class=""></span></div></b></div></div></div><div class=""><b style="font-family: Helvetica; orphans: 2; text-align: -webkit-auto; widows: 2;" class=""><font size="4" class="">Donna Brooms-Blue</font></b></div><div class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""><br class="Apple-interchange-newline" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;"><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;"><span><span><img apple-inline="yes" id="A310A858-3615-4E12-A1F8-E6C9D968B218" src="cid:E864EB6F-E291-4290-A25E-EB2464E6444D" class=""></span><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><b style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><br class=""></b><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">Department Secretary</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">Computer Science Department</span></span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;">John Crerar Library Building<br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">5730 So. Ellis Ave.</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">Chicago, IL. 60637</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">(773) 702-6614 - Office</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class="">(773) 702-8487 - Fax</span><br style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;" class=""><span style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; float: none; display: inline !important;" class=""><a href="mailto:donna@cs.uchicago.edu" class="">donna@cs.uchicago.edu</a></span></span></div>
</span></span></div>
</div></div></div></div></div></div><br class=""></body></html>