Circuit Depth Reductions
Circuit Depth Reductions
复制标题
电路深度减少
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Kulikov
中科院分区：
文献类型：
--
作者：
Alexander Golovnev;A. Kulikov
几十年来，对不受限制的赛道最知名的大小下限一直保持在30亿美元左右。此外，在这个模型中唯一已知的证明下界的技术，门消去法，本质上仅限于证明低于$5N$的下界。在这项工作中，我们提出了一种非门消去方法，通过确定的深度-三个下界来获得电路下界。我们证明了每一个大小为$S$的(无界深度)回路都可以表示为$2^{S/3.9}$$16$-CNF的OR。对于德摩根公式，最广为人知的尺寸下限几十年来一直停留在$n^{3-o(1)}$左右。在关于概率多项式的合理假设下，我们证明了$n^{4-varepsilon}$-Size DeMorgan公式有$2^{n^{1-Omega(Varepsilon)}}$-Size-3圈，它们是${mathbb F}_2$上$n^{1-Omega(Varepsilon)}$次多项式的近似和。虽然这些结构性结果不会立即导致新的下限，但它们确实表明了解决这些长期存在的下限问题的新途径。
我们的结果补充了Valiant的经典深度约简结果，后者表明线性大小的对数深度电路可以通过$2^{varepsilon n}${Delta}$-CNF的OR来计算，而对于串并联电路，我们的结果略强一些。众所周知，任何纯粹的图论归约都不能从超对数深度的电路中产生有趣的深度-3电路。我们通过同时考虑电路和公式的图论和功能属性来克服这一限制(对于小尺寸电路)。
我们证明了以下伪随机结构的改进隐含了新的电路下界：变量的离散子、与常次多项式的相关性、矩阵刚性和具有恒定底扇入的深度$3电路的硬度。
The best known size lower bounds against unrestricted circuits have remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we propose a non-gate-elimination approach for obtaining circuit lower bounds, via certain depth-three lower bounds. We prove that every (unbounded-depth) circuit of size $s$ can be expressed as an OR of $2^{s/3.9}$ $16$-CNFs. For DeMorgan formulas, the best known size lower bounds have been stuck at around $n^{3-o(1)}$ for decades. Under a plausible hypothesis about probabilistic polynomials, we show that $n^{4-varepsilon}$-size DeMorgan formulas have $2^{n^{1-Omega(varepsilon)}}$-size depth-3 circuits which are approximate sums of $n^{1-Omega(varepsilon)}$-degree polynomials over ${mathbb F}_2$. While these structural results do not immediately lead to new lower bounds, they do suggest new avenues of attack on these longstanding lower bound problems.
Our results complement the classical depth-$3$ reduction results of Valiant, which show that logarithmic-depth circuits of linear size can be computed by an OR of $2^{varepsilon n}$ $n^{delta}$-CNFs, and slightly stronger results for series-parallel circuits. It is known that no purely graph-theoretic reduction could yield interesting depth-3 circuits from circuits of super-logarithmic depth. We overcome this limitation (for small-size circuits) by taking into account both the graph-theoretic and functional properties of circuits and formulas.
We show that improvements of the following pseudorandom constructions imply new circuit lower bounds: dispersers for varieties, correlation with constant degree polynomials, matrix rigidity, and hardness for depth-$3$ circuits with constant bottom fan-in.
DOI：
--
发表时间：
2019
期刊：
23rd International Conference on Randomization and Computation (RANDOM
影响因子：
--
作者：
Zuckerman, D
通讯作者：
Zuckerman, D
线性布尔运算符的复杂性
DOI：
10.1561/0400000063
发表时间：
2013
期刊：
Found. Trends Theor. Comput. Sci.
影响因子：
--
作者：
S. Jukna;I. Sergeev
通讯作者：
I. Sergeev