For Better Performance Please Use Chrome or Firefox Web Browser

Computational Complexity

Homeworks will be handed out and in through IUT web course.

About the course: 

Computational Complexity theory looks at the computational resources (time, memory, communication, ...) needed to solve computational problems that we care about, and it is especially concerned with the distinction between "tractable" problems, that we can solve with reasonable amount of resources, and "intractable" problems, that are beyond the power of existing, or conceivable, computers. It also looks at the trade-offs and relationships between different "modes" of computation (what if we use randomness, what if we are happy with approximate, rather than exact, solutions, what if we are happy with a program that works only for most possible inputs, rather than being universally correct, and so on).

Outline of the course:

  1. Computational Models: Turing machines
  2. Deterministic and non-deterministic algorithms
  3. Time and space complexity
  4. Complexity classes: P, NP , co-NP, …
  5. Reductions and completeness: NP-complete problems
  6. Polynomial hierarchy
  7. Randomized computation
  8. Interactive proofs
  9. PCP theorem and approximability

and selected topics from the following list:

  1. Quantum computation
  2. Complexity of counting
  3. Average-case complexity
  4. Derandomization
  5. Decision tree
  6. Communication complexity


Main reference:

  • Arora S. and Barak B. Complexity Theory: A Modern Approach. 1st ed.: Cambridge University Press, 2009. ISBN-13: 978-0521424264.





All prerequisites will be covered. A decent knowledge about discrete mathematics will be fruitful.

Grading Policy: 

1 Midterm Exam (40%)

1 Final Exam (50%)

Homeworks (10%)

Projects (Optional)


Sundays and Tuesdays 13:00 - 15:00

Statistical Laboratory (Math. Department)

Fall 2014