Computer Science
Tel-Aviv University

0368.3168
Computational Complexity

Spring 2011

Announcements

[Aug 22] The final grade of Moed B was calculated as follows: the exam grade was multiplied by 1.08, and the final grade is min(100,max(EXAM, 0.85*EXAM+0.15*QUIZ)).
[Jul 11] The final grade was calculated as follows: the grade of Q1 is out of 10 points (so it should be multiplied by 2.5), the grade of Q3 is out of 20 points (so it should be multiplied by 1.25), the grade of Q4 is out of 25 points (so it should be added as is). The grade of Q3 consists of three grades corresponding to the three parts of the question, each of them is out of 5 (the first should be multiplied by 3, and the other two by 1.75). The final grade is min(100,max(EXAM, 0.85*EXAM+0.15*QUIZ)).
[Jun 8] The exam structure: four written-answer questions.
[Jun 6] The solution file was updated.
[May 17] The recitation class of May 24 (afternoon) is cancelled. We will have an extra recitation class on Sunday, June 5 at 16:00-17:00, 17:00-18:00, 18:00-19:00 in Lev auditorium.
[Mar 23] The quiz is available here and the grades are available here.
[Mar 1] The homework should be submitted to box 308 in Schreiber.
[Feb 27] A Google group for our course is available here. Thanks to Gilad!
[Feb 23] From now the lectures will be in Dach auditorium 005.
[Feb 22] The quiz will take place on March 22 and will be worth 15% of the final grade.

Homework assignments

Out	Due	Homework
22/2/2011	1/3/2011	Homework 1
1/3/2011	8/3/2011	Homework 2
8/3/2011	15/3/2011	Homework 3
16/3/2011	29/3/2011	Homework 4
29/3/2011	12/4/2011	Homework 5
14/4/2011	3/5/2011	Homework 6
3/5/2011	17/5/2011	Homework 7
18/5/2011	31/5/2011	Homework 8

Grade sheet

Some Information

Lectures

Tuesday 10:00-13:00, Dach 005
Recitations: Tuesday 15:00-16:00, 16:00-17:00, 18:00-19:00, Schreiber 008

Instructor

Amnon Ta-Shma | Schreiber 127 | 6405364

T.A.

Ishay Haviv

Lecture notes

PowerPoint presentations of Muli Safra.
Previous courses in TAU: Spring 2007, Spring 2008, Fall 2008, Spring 2009, Spring 2010
Oded Goldreich from Weizmann (see also here)

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

Homework assignments, quiz

Prerequisites

Computational models, Algorithms

Other links

A compendium of NP-complete problems and what's known about them.
A compendium of problems in higher levels of the hierarchy, part I and part II.
The zoo of all(?) known complexity classes.
Previous exams in our course

Schedule

Week	Date	Class Topics
1	Feb 22	Administration; the Turing machine model of computation [AB 1]; the time hierarchy theorem [AB 3.1]; oracle machines [AB 3.5]
		Multi-versus-single tape Turing machines [P 2.3, S 3.2]
2	Mar 1	Karp reductions versus Cook reductions; The class NP; Decision vs. Search [AB 2.5]; coNP [AB 2.6]
		IS is NP-complete; MAX-IS is NP-hard and coNP-hard
3	Mar 8	The Cook-Levin theorem [S 7.4]; Space bounded computation: CVAL is P-complete, log-space computation, PSPACE [AB 4.3, S 8.1]
		Padding argument: if P=NP then EXP=NEXP; there exists an oracle A in EXP such that EXP^A is not equal to EXP
4	Mar 15	Space complexity [AB 4, S 8]; L, NL; Savitch's theorem [AB 4.3, S 8.1]; Logspace Reductions, Composition in L [AB 4, S 8.1]; stCON is NL-complete [AB 4.4]; Immerman Theorem: NL=coNL [AB 4.4.2]
		Examples of NL-complete problems
5	Mar 22	Quiz; the polynomial-time hierarchy [AB 5.1]; TQBF [AB 4.3]
		An alternative definition of NL [AB 4.4.1]; 2SAT is in NL [P 9.2]
6	Mar 29	TQBF is PSpace-complete [AB 4.3]; Schoning's algorithm for 3SAT; Probabilistic complexity classes: RP, BPP [AB 7, P 11]; Amplification [AB 7.4, P 11.2]
		Σ₂ = NP^SAT [AB 5.5]
7	Apr 5	The Schwartz-Zippel lemma [AB 7]; Polynomial identity testing [AB 7.2.2]; Testing for perfect matching [AB 7.2.3]; BPP is contained in PSIZE [AB 7.6]; The Karp-Lipton Theorem [AB 6.2]
		Amplification of probabilistic complexity classes [AB 7.4, P 11.2]
8	Apr 12	BPP is contained in Σ₂ [AB 7.7, P 17.2]; Interactive proofs (IP) [AB 8.2]; AM [AB 8.4]; Graph Non-isomorphism [AB 8.3]
		Verifying matrix multiplication; if SAT is in BPP then SAT is in RP
9	May 3	IP is contained in PSpace [AB 8.5.3]; #3SAT is in IP [AB 8.5.2]; PCP; Approximation algorithms
		2-approximation algorithm for TSP with triangle inequality [V 3.2.2]; Graph Non-isomorphism [AB 8.3]
10	May 17	Approximation Algorithms: Vertex Cover [P 13.1], Set Cover [V 2.2.1]; Promise problems, Gap problems, Gap-preserving reductions
		1.5-approximation algorithm for TSP with triangle inequality [V 3.2.2]; Hardness of approximation of TSP without triangle inequality
11	May 24	The Constraint Satisfaction Problem (CSP) [AB 11.3]; the PCP theorem versus Max-3SAT [AB 11.3.1]
		Cancelled
12	May 31	Public key cryptography, El-Gammal system, the Discrete Log problem, A Personal View of Average-Case Complexity, El-Gammal as a commitment scheme, Coin flipping [AB 9.5.3], A computational zero knowledge proof for NP assuming an encryption scheme [AB 9.4], Summary
		The probabilistic method, Gap problems, Hardness of Gap problems implies hardness of approximation, applied to Max-E4SAT
13	Jun 5	The conditional expectation method

Computer Science Tel-Aviv University

0368.3168 Computational Complexity