Contents (hide) 5 Textbook

Welcome to Introduction to Computational Complexity homepage
Course Description
In this course we will study the basics of feasible computation and its limitations. Among the topics we will see: The classes P and NP.
 NP complete problems.
 Approximation algorithm, and hardness of approximation.
 Space bounded computation.
 Randomized algorithms and computational classes.
 Interactive proofs.
Course Schedule
Day  Time  Room 
Wednesday  12:0014:00  Building 32, Room 209 
Instructor
Name  Web page  Office  Office hours  
Ofer Neiman  http://www.cs.bgu.ac.il/~neimano  neimano at cs dot bgu dot ac dot il  Building 37, Room 215  Wed. 1012 
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, 80%. Students MUST PASS the exam to pass the course.The exam is with no supplementary material.
Homework assignments, 20%. There will be about 56 short homework assignments. These assignments do not include any programming.
There will be only one exam in the course (no MOED B).
You may hand in the exercises either by yourself or with one other student. Students whose partner has a valid reason not to hand in some assignment must still hand in the assignment. You may not hand in the assignments in groups larger than two. Cheating will not be tolerated. Cases of suspected cheating may result in the grade 0 on assignments and will be processed by the university disciplinary committee.