Bounded depth circuits: separating wires from gates

Abstrakt

We develop a new method to analyze the flow of communication in constant-depth circuits. This point of view allows us to prove new lower bounds on the number of wires required to recognize certain languages.