An exponential lower bound for depth two circuits with arbitrary symmetric gates in the bottom level and with a MOD/sub m/-gate in the top level is proved. This solves a problem posed by R. Smolensky (1990). The method uses the variation rank of communication matrices. A variant of this method is used for deriving lower bounds for the size of depth-two circuits having a threshold gate at the top.
展开▼
机译:证明了深度2电路的指数下界,深度2电路的底部是任意对称门,而顶部是MOD / sub m /门。这解决了R. Smolensky(1990)提出的问题。该方法使用通信矩阵的变化等级。此方法的一种变体用于推导深度为2的电路的下限,深度为2的电路的顶部为阈值门。
展开▼