Proving lower bounds on the amount of resources needed to compute specific functions is one of the most active branches of theoretical computer science. Significant progress has been made recently in proving lower bounds in two restricted models of Boolean circuits. One is the model of small depth circuits, and in this book Johan Torkel Håstad has developed very powerful techniques for proving exponential lower bounds on the size of small depth circuits' computing functions. The techniques described in Computational Limitations for Small Depth Circuits can be used to demonstrate almost optimal lower bounds on the size of small depth circuits computing several different functions, such as parity and majority. The main tool used in the proof of the lower bounds is a lemma, stating that any AND of small fanout OR gates can be converted into an OR of small fanout AND gates with high probability when random values are substituted for the variables. Håstad also applies this tool to relativized complexity, and discusses in great detail the computation of parity and majority in small depth circuits.
Contents
Introduction • Small Depth Circuits • Outline of Lower Bound Proofs • Main Lemma • Lower Bounds for Small Depth Circuits • Functions Requiring Depth k to Have Small Circuits • Applications to Relativized Complexity • How Well Can We Compute Parity in Small Depth? • Is Majority Harder than Parity? • Conclusions