Topics to be covered:

1. Deterministic vs Randomised Algorithms
2. P NP BPP L NL PSPACE etc. complexity classes
3. Interactive proofs and zero knowledge, bit commitment, one way functions, instance dependent bit commitment.
4. Random walks, zigzag product, undirected connectivity in L.
5. Other topics time permitting.

The textbook will be Arora and Barak's book "Computational complexity".