期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-78
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that for all constants a, NQP = NTIME[n polylog(n) ] cannot be (1/2 2 − loga n )- approximated by 2loga n -size ACC0 ◦ THR circuits (ACC0 circuits with a bottom layer of THR gates). Previously, it was even open whether E NP can be (1/2 1/√ n)-approximated by AC0 [⊕] circuits. As a straightforward application, we obtain an infinitely often (NE ∩ coNE)/1- computable pseudorandom generator for poly-size ACC0 circuits with seed length 2logε n , for all ε > 0. More generally, we establish a connection showing that, for a typical circuit class C , nontrivial nondeterministic algorithms estimating the acceptance probability of a given S-size C circuit with an additive error 1/S (we call it a CAPP algorithm) imply strong (1/2 1/n ω(1) ) average-case lower bounds for nondeterministic time classes against C circuits. Note that the existence of such (deterministic) algorithms is much weaker than the widely believed conjecture PromiseBPP = PromiseP. We also apply our results to several sub-classes of TC0 circuits. First, we show that for all k, NP cannot be (1/2 n −k )-approximated by n k -size Sum ◦ THR circuits (exact R-linear combination of threshold gates), improving the corresponding worst-case result in [Williams, CCC 2018]. Second, we establish strong average-case lower bounds and build (NE ∩ coNE)/1- computable PRGs for Sum ◦ PTF circuits, for various regimes of degrees. Third, we show that non-trivial CAPP algorithms for MAJ ◦ MAJ indeed already imply worst-case lower bounds for TC0 3 (MAJ ◦ MAJ ◦ MAJ). Since exponential lower bounds for MAJ ◦ MAJ are already known, this suggests TC0 3 lower bounds are probably within reach. 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 NC0 [Applebaum et al., SICOMP 2006], and Probabilistic Checkable Proofs of Proximity with NC1 - computable proofs.
