Computational Complexity Theory

0368-3168-01

[Monday 1-4pm, Orenstein 005 (Dach)]

 

 

 

 

[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

!!!A recent poly-time algorithm to check if a given number is prime
by M. Agrawal, N. Kayal and N. Saxena

Random Walks

Zero Knowledge Proofs


Message Board

Date 

Message

13/10/02

You can download a power point viewer from here.

13/10/02

Postscript (ps) viewer can be downloaded from here (For windows, choose gsv36w32.exe).

pdf viewer (acroread) can be downloaded from here.

13/10/02

Exercises are published on the web (see the above link).

16/10/02

There will be 2 quizzes during the semester: the 1st on 11/11/02, and the 2nd on 16/12/02.

31/10/02

You can find here last year’s quizzes and exam:

quiz1, quiz1 solutions, quiz2, quiz2 solutions, exam, exam solutions.

13/11/02

You can find here the quiz and the solutions.

31/12/02

You can find here the second quiz and the solutions.

19/01/03

You can find here exam 02a moed b and exam 02b.

06/02/03

You can find here the exam and the solutions of the multiple choice questions.