Back to TGINF

# Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Speaker: Lijie
Title: Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
Date: 25 Feb 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Food: Thai
Audience background:
Talk style:

Abstract: 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 strengthen 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. Finally, I will discuss some open questions stemmed from this work.