Computer Science
Tel-Aviv University

Computational Complexity Theory

0368.3168.01

Fall 2013/14


Classes


Requirements


Prerequisites


Announcements


Homework assignments


Forum


Previous Exams


Presentations


Recommended Reading


Schedule

Week

Class Topic

Recitaion Topic

Recitaion Notes

Homework

1

Introduction

Introduction

Complexity Functions

Turing Machines

P NP

Rec01-ppt

Rec01-pdf

HW1

2

Turing Machines

Basic Complexity Classes

Reductions

Multi-tape TM

Diagonalization

CoNP

Rec02-ppt

Rec02-pdf

HW2

3

Reductions (cont)

Space Complexity

NL

Savitch's Theorem

Padding Argument

NPC Reductions

NLC Reductions

Rec03-ppt

Rec03-pdf

HW3

4

Immerman's Theorem

Concentration of measure

C vs. coC

Space vs Time

NL and coNL

Rec04-ppt

Rec04-pdf

HW4

5

Approximation

Gap Problems

MaxCut Hardness

Gap Problems

MaxCut Approximation

MaxCut Derandomization

Rec05-ppt

Rec05-pdf

HW5

6

PCP Statement

Gap Preserving Reductions

Constraint Satisfaction Graphs

2SAT

Gap Preserving Reductions

MAX2SAT Hardness of Approximation

Rec06-ppt

Rec06-pdf

HW6

7

Gap Amplification

Polynomial Hierarchy

Constraint Satisfaction Graphs

Gap Amplification

Independent Set Approximation Hardness

Rec07-ppt

Rec07-pdf

No HW

8

Midterm

BPP

Midterm Solution

Student Questions

Rec08-ppt

Rec08-pdf

No HW

9

delta CSG

Unique Games

delta CSG

Rec09-ppt

Rec09-pdf

HW7

10

The Polynomial Hierarchy

BPP

The Polynomial Hierarchy

BPP

Rec10-ppt

Rec10-pdf

HW8

11

IP

Error Correcting Codes

Error Correcting Codes

Rec11-ppt

Rec11-pdf

HW9

12

Error Correcting Codes (cont)

Error Correcting Codes (cont)

Rec12-ppt

Rec12-pdf

HW10

13

14