Computer Science
Tel-Aviv University

Computational Complexity Theory

0368.3168.07

Spring 2013

 

Lectures

Tuesday 10:00-13:00, Dan David 1

Instructor

Amnon Ta-Shma | Schreiber 127 | 6405364

T.A

·         Michal Kleinbort. Office hour: Wednesday, 15:00-16:00. Please email if you plan to come.

·         Itay Berman. Office hour: Tuesday, 17:00-18:00. Please email if you plan to come.

Requirements

Prerequisites

Announcements

Forum

Final Exam

Midterm

 

Homework assignments

·  Homework submission is mandatory. However, you can submit an empty page (with your id only).

·  The final grade is not affected by the homework grade.

·  Submit Homeworks to the wooden box titled "Complexity" (number 5) near Shreiber 004-005.

·  Collect graded homeworks from the copy room.

·  To appeal, write your arguments and submit it together with the original homework, same as you submit homeworks.

·  Answered appeals can be collected from the copy room as well.

·  Homework submission list (for exercises 1-4)

 


Some Information

Textbooks

Main references:

[AB]

Computational Complexity: 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

Previous Exams

Previous exams

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.

Schedule

Date

Class Topic

Notes

Recitation Topic

Notes

1.

Feb 26

·   Administration;

·   Turing machine model of computation [AB 1];

·   Time hierarchy theorem [AB 3.1];

·   Circuits [AB 6.1]

·  Lecture 1

 

·         Simulating Muli-tape Turing machine by a single tape Turing machine with quadratic time overhead.

·    Recitation 1

2.

Mar 5

·         Oracle machines [AB 3.5]. 

·         Space complexity [AB 4, S 8];

·         L, PSPACE.

·         stCON is space(log^2n) [AB 4.2.1]; 

·         Lecture 2

·         Lecture 2a

·  The padding argument

·  Recitation 2

3.

Mar 12

·        Logspace Reductions, Composition in L [AB 4, S 8.1];

·  CVAL is P-complete under log-space reductions [6.7.2]

· Same as lecture 2

·  Boolean Circuits

·  Recitation 3

4.

Mar 19

·         TQBF is PSPACE-complete [AB 4.2]

·         2 definitions of NP [AB 2.1]

·      TQBF is PSPACE-complete

·  Recitation 4

5.

Apr 9

·    SAT, 3SAT [AB 2.3], 3NAE [P 9.2], 3COL [P Thm 9.8]

·    Search to decision reduction for SAT [AB 2.5]

·    coNP [AB 2.6]

·    The Languages Σ1-SAT, Π1-SAT [AB 5.2]

·  Lecture 5

·  NP and P are closed under *

·  NPC and Unary Languages

·  Recitation 5

6.

Apr 23

·  The polynomial time hierarchy [AB 5.2]

·  Lecture 6

·  SubsetSum is NP-Complete.

·  Recitation 6

7. Apr 30

·  Non-deterministic space [AB 4.1]

·  Savitch [AB 4.2]

·  Immerman [AB 4.3]

· Same as lecture 6

·  2 Definitions of NL.

·  Savitch, Immerman

·  Recitation 7

8.

May 7

·  Randomized computation.[AB 7.1]

·  RP [AB 7.3], BPP [AB 7.1]

·  RP in NP [AB 7.3]

·  Verifying matrix multiplication [MR 7.1]

·  A randomized algorithm for Perfect Matching [MR 7.3]

·  Lecture 8

· Amplifications of BPP.

·  Recitation 8

May 10

·  Quiz (1 hour, starting at 9:00)

9.

May 21

·  Randomized communication complexity of the equality function [AB EX. 13.15, AB p.130]

·  Sipser's theorem [AB 7.5]

·  Lecture 9

·  Karger's algorithm for min-cut

·  Recitation 9

10.

May 28

·  Approximation algorithms

·  Approximating VC (with maximal matching)

·  Approximating SetCover with the greedy algorithm (unit weights) [V 2.1]

·  Optimization problems and integer programming

·  Linear programming (LP), relaxations and rounding [V 13.1, 14.1, 14.2]

·  Approximating SetCover with a bounded number of occurrences of each item – with LP

·  Approximating the general SetCover problem - with LP

·  Goemans Williamson Max-Cut approximation (Not part of the exam material!)

·  Lecture 10

·  Sipser's theorem.

·  BPP is in P/poly.

·  Recitation 10

11.

Jun 4

·        Promise problems.

·        Gap problems.

·        GapMax3SAT is NP-hard. [AB 11.2]

·        NP hardness of gap problems vs. NP-hardness of 
approximation.

·        Gap preserving reductions.

·        Gap Max-Clique, GapMax-IS [AB 11.4]

·      Lecture 11

·      Lecture 11 (notes)

·  Approximating Weighted Set Cover

·  Recitation 11

12.

Jun 11

·                         Gap min-VC. [AB 11.4]
·                         The importance of location of the gap. 
·   Gap Max 3SAT[b] is NP-hard for some constant b. [V 29.4]

·  Lecture 12

·  MAX2SAT is hard to approximate for some constant factor.

·  Recitation 12

13.

Jun 18

·   The PCP theorem. [AB 11.2] 
·   GNISO has a long PCP system with only one query bit [AB 11.2.1]. 
·   CSP [AB 11.3.1]. 
·   Two equivalent views of the PCP theorem [AB 11.3].

·  Lecture 13

·  Constraint Satisfaction Problems

·  Recitation 13