Syllabus
1. Basic on Complexity Classes
  1.1 Theoretical models of computations and time and space resources
  1.2 Time and space complexity classes
  1.3 The P = NP problem
  1.4 NP and NP-completeness
  1.5 Unfeasible problems when resources are bounded
  1.6 Computational Classes: L, NL, P, NP, PSPACE, BPP, RP, #P, IP,
  1.7 Main Results
2.  Diagonalization
3.  Hierarchies Theorems for time, space, deterministic and non deterministic computations 
4.  Barriers Results I: Diagonalization is not sufficient to prove P different from NP 
5. Space Complexity 
   5.1 Shamir Theorem: PSPACE = IP
   5.2 Immerman-Szelepcsényi Theorem: NL=coNL, 
6. Boolean Circuits
 6.1 Basic definitions and efficient circuits  
 6.2 Bounded depth circuits: NC and AC hierarchies.
 6.3 Hastad-Razborov-Smolensky Theorem: Parity requires exponential size bounded depth circuits.
 6.4 Monotone Circuits
7. Polynomial Hierarchy and its basic theorems
8. Barriers Results - II
    8.1 Rudich-Razborov Theorem: "Natural proofs" are not sufficient to separate P from NP (unless crypto fails)
9. Other boolean models of computations and their limit: 
    9.1 Decision trees
    9.2 Branching programs. 
10. Introduction to Proof Complexity
  10.1. Logical proof systems: Resolution
  10.2 Geometric proof systems: Chvatal's cuts
  10.3 Algebraic proof system: Polynomial Calculus
  10.4 Semialgebraic proof systems: Sherali-Adams and Sum-of-Squares
  10.5 Exponential lower bounds for Resolution and Cutting planes: Ben-Sasson-Wigdeson width method and 
          Interpolation 
 
Bibliography
S. Arora B. Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2007
O. Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity Cambridge University Press 2010
O. Goldreich. Computational Complexity: A Conceptual Perspective  Cambridge University Press 2008.
A. Wigderson. Mathematics and Computation. Princeton University Press. In press
C. Papadimitriou. Computational Complexity. Pearsons. 1994.
S. Jukna.  Boolean Function Complexity. Springer. 2012
H. Vollmer. Introduction to Circuit Complexity: an uniform approach, Springer. 2013
J. Krajicek. Proof Complexity. Cambridge. 2019.

Final grade 
1. I quarter term blackboard presentations of a basic result.
2. Half-term homeworks
3. Final oral examinations.