Welcome to the Complexity homepage
|Tuesday||10:00-12:00||Building 34, Room 207|
|Wednesday||12:00-14:00||Building 90, Room 237|
|Name||Web page||Office||Office hours|
|Noga Ron-Zewi||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:00-16:00|
- S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.
- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 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 NP-completeness. 1979.
Grading PolicyFinal 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.