# 0368.3168 Computational Complexity

## Spring 2008

### Announcements

• [12/08/2008] The exams were graded and the grades will be published soon.
The exam and its solution are available in the Previous exams file.
Students that got grade in the range 52-59 and submitted good exercises passed the course.
The point distribution of each question is as follows:
Q1: a – 40%; b – 20%; c – 40%
Q2: a – 45%; b – 45%; c – 10%
Q3: a – 35%; b – 15%; c – 35%; d – 15%
Q4: a – 60%; b – 40%
• [20/07/2008] We will have a pre-exam recitation on July 30 at 16:00 in Dach auditorium.
• [16/07/2008] An optional exercise on OWF.
• [24/06/2008] The quiz and its solutions are in the exams file below. Grades.
• [17/06/2008] Homework 6: In Question 5b the word "maximal" should be "maximum".
You might prefer to wait with Question 6 until next week.
• [13/06/2008] In Homework 5, Question 4, the output-tape is unnecessary. Also, in Question 5a, s(|x|) should be s(n).
• [09/06/2008] The Monday group will have a quiz on June 23, and the Tuesday group will have a quiz on June 24.
• [03/06/2008] Notice that Homework 5 is for two weeks. The Tuesday group might prefer to wait with exercise 7 until next week.
• [20/05/2008] The Monday group has an extra class on Friday 23/05/2008 at 10:00.
• [20/05/2008] Graded exercises can be taken from Schreiber, room 114.
• [14/05/2008] From now on, the Tuesday lectures will take place in Orenstein 103.
• [07/05/2008] In Homework 1, Question 1a (for submission) the gates can have large fan-in.
• [04/05/2008] The recitation of May 6 at 18:00-19:00 is cancelled due to the Memorial Day.
Instead, a recitation will be given on May 6 at 17:00-18:00 in Physics Shenkar 104 (in addition to the recitations at 15:00 and 16:00).

### Some Information

Lectures

Group 1: Monday 10:00-13:00, Orenstein 103
Group 2: Tuesday 10:00-13:00, Orenstein 103
Recitations: Tuesday 15:00-16:00, 16:00-17:00 Kaplun 118, 18:00-19:00 Schreiber 008.

Instructors

Oded Regev | Schreiber 103 | 6407996
Amnon Ta-Shma | Schreiber 127 | 6405364
T.A.: Ishay Haviv

Lecture notes on the web

Previous courses in TAU by Muli Safra, Amnon Ta-Shma
Steven Rudich from CMU

Textbooks

Main references:

 [AB] Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak [S] Introduction to the Theory of Computation, by Michael Sipser (1st or 2nd edition only) [P] Computational Complexity, by Christos H. Papadimitriou

Other textbooks:

 [MOV] Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone. [MR] Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan [V] Approximation Algorithms, by Vijay V. Vazirani [CLR] Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest

Requirements

Attendance, homework assignments, quiz

Prerequisites

Computational models, Algorithms