Contents (hide)

Welcome to the Complexity homepage

Course Schedule

Day Time Room
Tuesday 10:00-12:00Building 34, Room 207
Wednesday12:00-14:00Building 90, Room 237


Name Web page E-mail Office Office hours
Noga Ron-Zewi nogazewi at cs dot bgu dot ac dot il Building 37, Room 111 By email appointment
Eden Chlamtáč chlamtac at cs dot bgu dot ac dot il Building 37, Room 210 Tue. 14:00-16:00


  1. S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.

Other Textbooks

  1. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
  2. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  3. J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
  4. M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NP-completeness. 1979.

Grading Policy

Final exam, 70%. Students MUST PASS the exam to pass the course.
The exam is with no supplementary material.

There will be only one exam in the course (no MOED B).

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.