Course Description
We will start this course by mathematically formalizing computation and algorithms. Our approach in the course would be to look at famous concrete problems and prove theorems about their uncomputability, or, if computable, then how fast can they be computationally solved.
The problems we will cover in this course are: the halting problem, boolean formula satisfiability (the P!=NP question), quantified boolean formula, formula minimization, polynomial identity testing, undirected graph reachability, permanent and graph isomorphism. While studying these computational problems we will define various complexity classes and develop various tools used in modern complexity theory.
Preferred Prerequisites: Theory of Computation.
Text Book: Arora & Barak, Computational Complexity (Cambridge University Press)
Course Content
FUNDAMENTALS.
- Turing machine
- Non-deterministic time
- Time/Space Hierarchy
- Space complexity
- Counting complexity classes
- Randomization
- Circuits
- Interaction
ADVANCED TOPIC IDEAS.
- you choose a paper/result
- Matiyasevich's proof of Hilbert's 10th problem
- Reingold's graph reachability in logspace
- AKS' primality test
- Hastad's parity is not in AC_0
- Williams' NEXP is not in ACC_0
- Razborov-Rudich's natural proof barrier
- Aaronson-Wigderson's algebrization barrier
Course Audience
Students interested in maths, theory; or simply those curious about hard problems.