Communication in bounded depth circuits
Communication in bounded depth circuits
复制标题
有界深度电路中的通信
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
P. Pudlák
中科院分区：
文献类型：
--
作者：
P. Pudlák
我们证明了矩阵的刚性可以用来证明深度为2的电路和通信图的下界。我们证明了一个一般的非线性界上的某种类型的电路，因此，特别是，我们确定的渐近大小depthd超集中器的所有深度≥4（甚至深度≥4之前已经确定）。
We show that rigidity of matrices can be used to prove lower bounds on depth 2 circuits and communication graphs. We prove a general nonlinear bound on a certain type of circuits and thus, in particular, we determine the asymptotic size of depthd superconcentrators for all depths ≥4 (for even depths ≥4 it has been determined before).