Contents (hide) 4 Textbook

Welcome to the Complexity homepage
Course Schedule
Day  Time  Room 
Tuesday  10:0012:00  Building 34, Room 207 
Wednesday  12:0014:00  Building 90, Room 237 
Instructors
Name  Web page  Office  Office hours  
Noga RonZewi  http://www.cs.bgu.ac.il/~nogazewi  nogazewi at cs dot bgu dot ac dot il  Building 37, Room 111  By email appointment 
Eden Chlamtáč  http://www.cs.bgu.ac.il/~chlamtac  chlamtac at cs dot bgu dot ac dot il  Building 37, Room 210  Tue. 14:0016:00 
Textbook
 S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.
Other Textbooks
 M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
 C. H. Papadimitriou. Computational Complexity. AddisonWesley, 1994.
 J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
 M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NPcompleteness. 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 45 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.