At present the following three sets of notes are available. If you have some course notes which you would like to add to the series, please contact the Editor of the Newsletter.
The second part of the course is devoted to results on interactive proofs. Arthur-Merlin games are studied and shown to recognize all languages in PSPACE. Two prover interactive proof systems and their relationship with the probabilistically checkable proofs (PCP) is described. The characterization of {\bf NP} in terms of PCP, as well as some of its consequences to approximation algorithms, is presented in detail.
The main focus of the course is Circuit Complexity. We motivate the area through illustrative examples for the constant-depth circuit classes. Circuit implementations for the Threshold, Addition, Multiplication, Iterated Addition and Iterated Multiplication are presented with this objective in mind. A few results from Number Theory are discussed along the line.
The course then gives a bird's eye view of Computational Complexity Theory. It then winds its way through Brent's result on expression trees, Barrington's result on Bounded Width Branching Programs and Ben-Or and Cleve's result on the evaluation of expression trees using 3 registers. We then move on to Savitch's Theorem and the Immerman and Szelepscenyi result.
The course then ventures on to Haastad's Switching Lemma. We motivate and prove this beautiful result that shows PARITY is not in AC${}^0$ . In the same vein we present the Voting Polynomials of Aspens et al. Razborov's Method of Approximations with its ethereal Sunflower Lemma is reserved for the end.
This is an introduction to logic oriented towards the use of logic in computer science. In this course, we discuss techniques and results from propositional logic, modal logic, propositional dynamic logic and first-order logic.
At present, the sections on propositional and modal logic are ready. A complete set of notes should be available by April, 1998.