Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits
Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits
复制标题
对于 ACC 电路来说，非确定性拟多项式时间在平均情况下是困难的
DOI：
10.1109/focs.2019.00079
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Lijie Chen
中科院分区：
文献类型：
--
作者：
Lijie Chen
继[威廉姆斯，J. ACM 2014]的开创性工作之后，在最近的一项突破中，[Murray和威廉姆斯，STOC 2018]证明了NQP（非确定性准多项式时间）不具有多项式大小的ACC ^0电路。通过证明对于所有常数c，NQP中存在一种语言，它不是多项式大小的ACC ^0电路1/2+1/log^c（n）-可逼近的，我们将上述下界加强到平均情况下的下界。事实上，我们的下限适用于更大的电路类：2^（log^an）-大小的ACC ^0电路，底部有一层阈值门，对于所有常数a。我们的工作还改进了NEXP对多项式大小ACC电路的平均情况下限[Chen，Oliveira和Santhanam，拉丁语2018]。我们的新下界建立在几个有趣的组成部分上，包括：·巴林顿定理和随机自约的NC ^1-完备语言的存在性。·NE相对于ACC ^0的次指数大小下限和[威廉姆斯，SICOMP 2016]中的条件非确定性PRG构造。·一个“几乎”几乎处处MA平均情况下的下界（这加强了[Murray and威廉姆斯，STOC 2018]中相应的最坏情况下的下界）。一种PSPACE完备的语言，它是相同长度的可检查的，可纠错的，并且还具有一些其他很好的归约属性，它建立在[Trevisan和Vadhan，Computational Complexity 2007]的基础上。此外，它的所有约简性质都有相应的低深度非自适应预言电路。与通过"算法方法“证明的其他下界一样，我们利用的THR的ACC^0的唯一性质是THR的ACC^0的非平凡SAT算法的存在[威廉姆斯，STOC 2014]。因此，对于任何典型的电路类，如果发现相应的非平凡SAT（实际上，GAP-UNSAT）算法，我们的结果也适用于它们。
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 NQP, 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 circuits by [Chen, Oliveira, and Santhanam, LATIN 2018]. Our new lower bound builds on several interesting components, including: • Barrington's theorem and the existence of an NC^1-complete language which is random self-reducible. • The sub-exponential witness-size lower bound for NE against ACC^0 and the conditional non-deterministic PRG construction in [Williams, SICOMP 2016]. • An “almost'' almost-everywhere MA average-case lower bound (which strengthens the corresponding worst-case lower bound in [Murray and Williams, STOC 2018]). A PSPACE-complete language which is same-length checkable, error-correctable and also has some other nice reducibility properties, which builds on [Trevisan and Vadhan, Computational Complexity 2007]. Moreover, all its reducibility properties have corresponding low-depth non-adaptive oracle circuits. Like other lower bounds proved via the ``algorithmic approach'', the only property of ACC^0 of THR exploited by us is the existence of a non-trivial SAT algorithm for ACC^0 of THR [Williams, STOC 2014]. Therefore, for any typical circuit class ℓ, our results apply to them as well if the corresponding non-trivial SAT (in fact, GAP-UNSAT) algorithms are discovered.
AC0[p] 通过硬币问题针对 MCSP 的下界
DOI：
--
发表时间：
2019
期刊：
ICALP
影响因子：
--
作者：
Golovnev, Alexander;Ilango, Rahul;Impagliazzo, Russell;Kabanets, Valentine;Kolokolova, Antonina;Tal, Avishay
通讯作者：
Tal, Avishay
具有建议的自适应程序的不可区分性以及硬度放大证明的下限
DOI：
10.1109/focs.2018.00094
发表时间：
2018
期刊：
FOCS
影响因子：
--
作者：
Grinberg, Aryeh;Shaltiel, Ronen;Viola, Emanuele
通讯作者：
Viola, Emanuele