Borel sets and circuit complexity
Michael Sipser · 1983
It is shown that for every k, polynomial-size, depth-k Boolean circuits are more powerful than polynomial-size, depth-(k−1) Boolean circuits. Connections with a problem about Borel sets and other questions are discussed.