Computer Science
Tel-Aviv University

Computational Complexity Theory

0368.3168.01

Winter 2012/13


Classes


Requirements


Prerequisites


Announcements


Homework assignments


Forum


Previous Exams


Presentations


Recommended Reading


Schedule

Week

Class Topic

Recitaion Topic

Recitaion Notes

HomeWork

1

Introduction

Turing Machines

Introduction

Complexity Functions

Turing Machines

Recitation1

HW1

2

Basic Complexity Classes

P and NP

Karp reductions

Recitation2

HW2

3

NPC

Cook-Levin theorem

NPC

Recitation3

HW3

4

Space complexity

NL

Savitch's Theorem

The Padding Argument

Definitions of NL

Recitation4

HW4

5

Immerman's Theorem

Immerman's Theorem (proof again)

Savitch and some examples

Recitation5

HW5

6

Approximation algorithms: vertex Cover, independent set, TSP

Definition of gap problems

Greedy algorithm for approximation of MinVC

Gap problem of MaxCut

Recitation6

HW6

7

The PCP theorem: hardness of approximation

Hardness of approximation of MAX2SAT

Recitation7

HW7

8

CSG and Amplification

Clique approximation is hard to any factor

CSG and Amplification

Recitation8

No HomeWork

9

TQBF is PSPACE-Complete

Quiz

SubsetSum is NPC

Gap-SubsetSum[1-e,1] is easy

Recitation9

HW8


10

BPP, PH

BPP is in Sigma2

BPP Amplification

Recitation10

HW10


11



Approximation factor 3/2 for TSP with triangle enequality

Uniqueness in triplets

Recitation11

HW11

12

Hardness of approximation of coloring

Random walks

Reproof the reduction from kCSG to qGSG_Delta

Recitation12


13

Error Correcting Codes

2SAT is in NL (NLC)

Unique-Game

Recitation13

HW13

14

Error Corecting codes

Error correcting codes

Random codes

Recitation14

No HW