Bounded-depth circuits
Michal Koucký, Pavel Pudlák, Denis Thérien · 2005
We develop a new method to analyze the flow of communication in constant-depth circuits. This point of view allows usto prove new lower bounds on the number of wires required to recognize certain languages. We are able to provide explicit languages that can be recognized by AC0 circuits with O(n) gates but not with O(n) wires, and similarly for ACC0 circuits. We are also able to characterize exactly the regular languages that can be recognized with O(n) wires, both in AC0 and ACC0 framework.