Computational Complexity Theory

0368-3168-01

[Thursday 9am- 12pm]

[Syllabus]

[Messages]

[Exercises]

Presentations:

Introduction

Preliminaries; Reductions

Cook Theorem

NP-complete Problems;

Paths; 2SAT

Space Complexity

Approximation Algorithms; TSP;

Hardness of Approximation

Cryptography

The Polynomial-time Hierarchy and BPP

coNP and Primality

Random Walks

Zero Knowledge Proofs