On the Power of Small-Depth Computation

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 (AC⁰) 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.