Advanced aspects of computational complexity 1000-2M24ZAZ
1) Polynomial hierarchy. SAT cannot be solved in linear time and sublinear space.
2) Karp-Lipton and Meter theorems – polynomial hierarchy vs non-uniform circuits.
3) BPP vs polynomial hierarchy.
4) Polynomial hierarchy vs counting problems. Toda’s theorem.
5) Interactive proofs – an alternative definition of polynomial space.
6) Computational security, one-way functions, and pseudorandom generators.
7) Quantum computation (the basics).
8) PCP theorem and hardness of approximation.
9) Proof complexity.
10) Expander graphs and their application to pseudorandom generators.
11) Natural proofs.
12) Computational complexity vs logic. Fagin’s and Immerman-Vardi theorems.
Prerequisites
Course coordinators
Assessment criteria
Oral exam. In addition, increasing of the final mark is possible due to solving star problems. Each problem is worth 1 divided by the number of students who correctly solved it.
For PhD students: obligatory participation in solving of star problems, or reading recent literature.
Bibliography
• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.
• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press 2009 (available on-line)
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: