[Colloquium] Theory speaker Lijie Chen (MIT)

[Donna Brooms]

REMINDER:

Department of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, December 3, 2019
Ryerson 251@ 3:30 pm
  
Lijie Chen
MIT
http://www.mit.edu/lijieche/
 

Title: “Strong Average-Case Lower Bounds from Non-trivial Derandomization”

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. 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.

Host: Prof. Andrew Drucker

(Refreshments will be served prior to the talk at 3:15 pm in Ry. 257)


Donna Brooms-Blue



Department Secretary
Computer Science Department
John Crerar Library Building
5730 So. Ellis Ave.
Chicago, IL. 60637
(773) 702-6614 - Office
(773) 702-8487 - Fax
donna at cs.uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191203/1d37eef2/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 2340 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191203/1d37eef2/attachment-0001.gif>