Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
复制标题
来自本地伪随机发生器的 MCSP 电路下界
DOI：
10.1145/3404860
复制
发表时间：
2020
影响因子：
0.7
通讯作者：
Cheraghchi M
中科院分区：
文献类型：
--
作者：
Cheraghchi M
最小电路尺寸问题（MCSP）询问对于给定的参数θ，布尔函数f的给定真值表是否可以通过尺寸最多为θ的布尔电路来计算。我们改进了MCSP的几个电路下界，使用伪随机发生器（PRG）是本地的; PRG被称为本地的，如果它的输出位串，当被视为一个布尔函数的真值表，可以计算的布尔电路的小尺寸。我们得到了新的和改进的下限MCSP几乎匹配最知名的下限对几个电路模型。具体来说，我们证明了在具有长度为N的真值表的函数上计算MCSP需要·N3−o（1）-size de Morgan公式，改进了Hirahara和Santhanam最近提出的N2 −o（1）下界（CCC，2017），·N2−o（1）-大小公式在任意基或一般分支程序（MCSP对这些模型没有已知的非平凡下限），和· 2Ω（N1/（d+1.01））大小的深度dAC 0电路，改进了Allender等人的（隐含的，在他们的工作中）指数大小下限。（SICOMP，2006）。上述AC 0下限与最著名的AC 0下限（对于奇偶性）相匹配，直到深度上的一个小的加性常数。此外，对于深度2电路的特殊情况（即，CNFs或DNF），我们得到了MCSP的最佳下界为2Ω（N）。
The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean functionfcan be computed by a Boolean circuit of size at most θ, for a given parameter θ. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is calledlocalif its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of lengthN, requires•N3−o(1)-size de Morgan formulas, improving the recentN2−o(1)lower bound by Hirahara and Santhanam (CCC, 2017),•N2−o(1)-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and• 2Ω(N1/(d+1.01))-size depth-dAC0circuits, improving the (implicit, in their work) exponential size lower bound by Allender et al. (SICOMP, 2006).The AC0lower bound stated above matches the best-known AC0lower bound (for PARITY) up to a smalladditiveconstant in the depth. Also, for the special case of depth-2 circuits (i.e., CNFs or DNFs), we get an optimal lower bound of 2Ω(N)for MCSP.
登录
查看更多内容
回顾 Luby-Veličković-Wigderson：改进深度二电路的相关界限和伪随机生成器
DOI：
10.4230/lipics.approx-random.2018.56
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
R. Servedio;Li
通讯作者：
Li
迈向 KRW 组成猜想：通过通信复杂性得出三次公式下界
影响因子：
1.4
作者：
Irit Dinur;Or Meir
通讯作者：
Or Meir
具有少量任意对称门的恒定深度电路的伪随机位
DOI：
10.1137/050640941
发表时间：
2005
期刊：
20th Annual IEEE Conference on Computational Complexity (CCC'05)
影响因子：
--
作者：
Emanuele Viola
通讯作者：
Emanuele Viola
学习算法、电路下界和伪随机性之间的阴谋
DOI：
10.4230/lipics.ccc.2017.18
发表时间：
2016
期刊：
SIAM J. Comput.
影响因子：
--
作者：
I. Oliveira;R. Santhanam
通讯作者：
R. Santhanam
从自然证明中学习算法
DOI：
10.4230/lipics.ccc.2016.10
发表时间：
2016
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
M. Carmosino;R. Impagliazzo;Valentine Kabanets;A. Kolokolova
通讯作者：
A. Kolokolova