Syllabus
Boolean circuits and P/poly coNEXP is not in NEXP/poly
NP^NP does not have circuit of size O(n^k), for fixed k
Logarithmic depth circuit, Boolean formulas
Constant depth circuits
Parity not in AC0 - proofs of Razborov and Smolensky
Approximating MAJ in AC0
ACC0 vs CC0
Circuit depth reductions
Williams: NEXP is not in ACC0
Branching programs and their relationship to space bounded computation
Barrington's Theorem
Generalization of Barrington's Theorem for arithmetic formulas
Catalytic computation
Annotation
This course extends the basic course on computational complexity (NTIN063). It covers various types of Boolean circuits and branching programs, their relationships and relationships to the usual complexity classes.