In this monograph we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain:
A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0,1}.
An unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones.
Valiant’s simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full.
Applebaum, Ishai, and Kushilevitz’s cryptography in bounded depth.