Bounded-Depth Circuits Cannot Sample Good Codes
Bounded-Depth Circuits Cannot Sample Good Codes
复制标题
有界深度电路无法采样好的代码
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Shachar Lovett;Emanuele Viola
我们研究了经典电路下界问题的一个变种：证明随机比特抽样分布的下界。我们证明了1−1/nΩ(1)关于(I)任意小的恒定深度的输出分布之间的统计距离的下界。Ac0)电路f：{0，1}Poly(N)→{0，1}n，以及(Ii)在任意码$${Mathcal{C}子集q{0，1}^n}$$上的均匀分布，即具有相对距离和速率Ω(1)。我们给出了这一结果的两个简单应用：(1)任何用于存储好码$${mathcal{C}子集{0，1}^n}$$的码字的数据结构都需要冗余对数(Ωn)，如果码字的每一位都可以被一个小的ac0电路取回；(2)对于一些潜在的组合设计，对于深度d的ac0电路，Nisan的伪随机发生器的输出分布不能被深度小于d的小ac0电路采样。
We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of 1 − 1/nΩ(1) on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a. AC0) circuit f : {0, 1}poly(n) → {0, 1}n, and (ii) the uniform distribution over any code $${mathcal{C} subseteq {0, 1}^n}$$ that is “good,” that is, has relative distance and rate both Ω(1). This seems to be the first lower bound of this kind.We give two simple applications of this result: (1) any data structure for storing codewords of a good code $${mathcal{C} subseteq {0, 1}^n}$$ requires redundancy Ω(log n), if each bit of the codeword can be retrieved by a small AC0 circuit; and (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan’s pseudorandom generator against AC0 circuits of depth d cannot be sampled by small AC0 circuits of depth less than d.