Bounded depth circuits: separating wires from gates

Abstract

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.

Keywords

• Bounded
• depth
• circuits
• separating
• wires
• gates