COMMUNICATION IN BOUNDED DEPTH CIRCUITS

被引：47

作者：

PUDLAK, P ^{[1
]}

机构：

[1] AVCR,MATEMAT USTAV,CS-11567 PRAGUE 1,CZECH REPUBLIC

来源：

COMBINATORICA | 1994年 / 14卷 / 02期

关键词：

AMS subject classification code (1991): 68R10; 05C35;

D O I：

10.1007/BF01215351

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 depth d superconcentrators for all depths greater-than-or-equal-to 4 (for even depths greater-than-or-equal-to 4 it has been determined before).

引用

页码：203 / 216

页数：14

共 10 条

[1] SUPERCONCENTRATORS OF DEPTH-2 AND DEPTH-3 - ODD LEVELS HELP (RARELY) [J].