Computational Limitations for Small Depth Circuits

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 Hastad 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.Hastad 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.John Hastad is a postdoctoral fellow in the Department of Mathematics at MIT C"omputational Limitations of Small Depth Circuits" is a winner of the 1986 ACM Doctoral Dissertation Award.