<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div class=""><div class=""><div class=""><div class=""><b style="background-color: rgba(255, 255, 255, 0);">Lijie Chen</b></div><div class=""><b style="background-color: rgba(255, 255, 255, 0);">MIT</b></div><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);"><br class=""></b></div><div class=""><b class=""><a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="text-decoration-color: rgba(0, 0, 0, 0.258824); background-color: rgba(255, 255, 255, 0);">Tuesday, December 3, 2019</a></b></div><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);">Ryerson 251 <a href="x-apple-data-detectors://2" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="2" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">@ 3:30pm</a></b></div></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><b class="">Title: </b>Strong Average-Case Lower Bounds from Non-trivial Derandomization</span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);">Abstract: 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.</span></div><p style="margin: 0px; font-stretch: normal; line-height: normal; min-height: 13.8px;"><span style="background-color: rgba(255, 255, 255, 0);"> </span></p><p style="margin: 0px; font-stretch: normal; line-height: normal;"><span style="background-color: rgba(255, 255, 255, 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.</span></p><p style="margin: 0px; font-stretch: normal; line-height: normal; min-height: 13.8px;"><span style="background-color: rgba(255, 255, 255, 0);"><br></span></p><p style="margin: 0px; font-stretch: normal; line-height: normal;"><span style="background-color: rgba(255, 255, 255, 0);">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.</span></p><p style="margin: 0px; font-stretch: normal; line-height: normal; min-height: 13.8px;"><span style="background-color: rgba(255, 255, 255, 0);"><br></span></p><p style="margin: 0px; font-stretch: normal; line-height: normal;"><span style="background-color: rgba(255, 255, 255, 0);">This is joint work with Hanlin Ren from Tsinghua University.</span></p><p style="margin: 0px; font-stretch: normal; line-height: normal; min-height: 13.8px;"><span style="background-color: rgba(255, 255, 255, 0);"><br></span></p><p style="margin: 0px; font-stretch: normal; line-height: normal;"><span style="background-color: rgba(255, 255, 255, 0);">Refreshments will be served prior to the talk <a href="x-apple-data-detectors://6" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="6" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">at 3:15 pm</a> Ry 257.</span></p></div></div><div dir="ltr"></div></body></html>