Contents (hide)

Welcome to the Complexity homepage

Course Schedule

Day Time Room
Tuesday 10:00-12:00Building 90, Room 137
Wednesday12:00-14:00Building 90, Room 323


Name Web page E-mail Office Office hours
Or Sattath sattath at cs dot bgu dot ac dot il Building 37, Room 120 Sunday 9:00-11:00
Eden Chlamtáč chlamtac at cs dot bgu dot ac dot il Building 37, Room 210 Tuesday 14:00-16:00


  1. S. Arora, B. Barak. Quantum Computation and Quantum Information, Cambridge University Press, 2000.

For introduction to classical computational complexity, we recommend "Introduction to the theory of computation" by Michael Sipser.

Grading Policy

At the end of the semester, the students are required to give an oral presentation of a research paper. The preparation and presentation is done in pairs, and consists of 70% of the final grade.
Homework assignments, 30%. There will be about 4-5 homework assignments.

All assignments are mandatory, and must be handed in individually. You may discuss the assignments with each other – we actively encourage open discussion and collaboration on the assignments! However, you must write and hand in your own solution in your own words.