The NP-completeness of SAT is a celebrated example of the power of bounded-depth computation: the core of the argument is a depth reduction establishing that any small nondeterministic circuit - an arbitrary NP computation on an arbitrary input - can be simulated by a small non deterministic circuit of depth 2 with unbounded fan-in - a SAT instance. Many other examples permeate theoretical computer science. On the Power of Small-Depth Computation discusses a selected subset of them, and includes a few unpublished proofs. On the Power of Small-Depth Computation starts with a unified treatment...