Complexity of Random Operators in Circuits With Arbitrary Gates

Abstract

In this note we consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n.
As gates we allow arbitrary(!) boolean functions; neither fanin nor fanout of gates is restricted.
An operator is linear if it computes n linear forms, that is, computes a matrix-vector product Ax over GF(2).
We prove the existence of:

• n-operators requiring about n^2 wires in any circuit, and
• linear n-operators requiring about n^2/\log n wires in depth-2 circuits, if either all output gates or all gates on the middle layer are linear.