Complexity Theory  - Winter 2004/5

          To:     Bibliography and references        Homework         Handouts and Slides

Moni Naor 

Grader: Asaf Nussbaum

When:     Thursday 14:00--17:00
Where:    Ziskind 1

DESCRIPTION:   Computational complexity studies the inherent resources needed to perform various computational tasks. Typical resources are time and memory, but other measures are of interest as well, such as parallelism, communication and randomness. The goal of the course is to provide a firm foundation of the field.

PREREQUISITES: Students are expected to be familiar with algorithms, data structures, probability theory, and linear algebra, at an undergraduate level; a basic course in computability is assumed.

METHOD OF EVALUATION: There will be around ten homework assignments and a final test. Homework assignments should be turned in on time (usually two weeks after they are given)! Try and do as many problems from each set. You may (and are encouraged to) discuss the problems with other students, but the write-up MUST be individual.

Exam : The exam will be in class.

BIBLIOGRAPHY: There is no textbook for the course. A lot of background and relevant material is available in 

   Online  courses close in nature to our course:

     Bibliography on specific topics (communication complexity, randomization):

     Important Web Resources on Complexity: