# Complexity (89-320)

## (2013)

## General Information

**Semester A**

**Lecturer:** Yair Dombb

Tuesday, 12:00-14:00, **Building:**
605, 11

**Teaching Assistant:** Gilad Asharov

Tuesday, 14:00-15:00, **Building:**
505, 61

** Grades: ** 90% final exam,

5% Quiz I

5% Quiz II

What if I cannot attend one (or both) of the quizzes?

** Important dates:** 19.11 Quiz I

24.12 Quiz II

## Recitation Notes

Rec1 (23/10 - self reducibility)

Rec2 (30/10 - P, NP, NPC, coNP)

Rec3 (06/11 - Integer Programming. Thanks to Hila Zarosim!)

Rec4 (13/11 - The Polynomial Hierarchy (I))

Rec5 (20/11 - The Polynomial Hierarchy (II))

Rec6 (27/11 - Space Complexity (I))

Rec7 (04/12 - Space Complexity (II))

Rec8 (11/12 - P/Poly)

Rec9 (18/12 - Randomized Algorithms)

rec10 (25/12 - Randomized Computation(I))

Rec11 (01/01 - Randomized Computation(II))

Rec12 (08/01 - PCP and Hardness of Approximation(I))

Rec13 (15/01 - PCP(II))

## Exercises

(not for submission)

Exercise 1 (sol) additional question (sol)

Exercise 2 (sol) additional questions (sol)

Exercise 3 (sol)

Exercise 4 (sol)

Exercise 5 (sol)

Exercise 6 (sol)

Exercise 7 (sol)

Exercise 8 (sol)

Exercise 9 (sol)

Exercise 10 (sol)

Exercise 11 (sol)

Exercise 12 (sol)

## Grades

Quiz 1 + 2

## Quizes

Quiz1

Quiz2

## Exam

Exam A (sol)

## Announcements

**10.02** : Please look at the followig file regarding the exam here