An introduction to circuit complexity and a guide to Håstad's proof

Abstract: "This report provides a complete exposition of the main proof in Johan Håstad's thesis [Hås87]. The result gives a lower bound on the size of certain Boolean circuits computing the PARITY function, and it implies that [formula]. Every effort has been made to make the proof understandable for someone with no background in the area of theoretical circuit complexity. To that end, the report begins by introducing the basic definitions and classes of the field. The proof is then motivated by a section explaining why circuits are of interest to theoretical computer scientists. Before stating and proving Håstad's result, some preliminary concepts are presented.These ideas are the b̀uilding blocks' of the proof itself. A brief history of related result is given. Then, an intuitive description of the proof and a r̀oad map' of its structure (which has several levels and branches) are presented to provide an overall gist of what is going on behind the formal mathematics which follow. The heart of the proof is the so-called S̀witching Lemma', which is given considerableattention. The main result and a corollary are then stated and proven."