Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
April 17, 2019 (GHC 8102)

Following the seminal work of (Williams, J. ACM 2014), in a recent breakthrough, (Murray and Williams, STOC 2018) proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits. We strength the above lower bound to an average case one, by proving that for all constants c, there is a language in non-deterministic quasi-polynomial time, which is not (1/2+1/log^c n)-approximable by polynomial-size ACC^0 circuits. In fact, our lower bound holds for a larger circuit class: 2^(log^a n)-size ACC^0 circuits with a layer of threshold gates at the bottom, for all constants a. Our work also improves the average-case lower bound for NEXP against polynomial-size ACC^0 circuits by [Chen, Oliveira, and Santhanam, LATIN 2018]. In the first part of the talk, I will try to explain the difficulty of proving an average-case lower bound along the previous proof paradigm, and then outline the structure of the new average-case lower bound proof. One key ingredient of the proof is a new almost almost-everywhere (a.a.e.) MA circuit lower bound with very sophisticated properties. I will then try to motivate why we need such an MA circuit lower bound, and present a proof for a toy version of that if time permits. Finally, I will discuss some open questions stemmed from this work.