Home | Course Info | Assignments | Syllabus And Lectures | Staff and Hours | LaTeX

Calendar
Month Mon Wed
Jan   21 Overview of the Course
Jan 26 Models of Computation 28 Classes P and NP
Feb 2 NP-Complete Languages 4 Space Complexity
Feb 9 Complements of Classes 11 PSPACE-Complete Languages
Feb 16 Holiday 18 Diagonalization & Reductions
Feb 23 Limits on Diagonalization 25 Circuits
Mar 2 Circuits 4 Formula Size
Mar 9 Space-Time Tradeoffs I 11 Space-Time Tradeoffs II
Mar 16 Space-Time Tradeoffs III 18 Space-Time Tradeoffs IV
Mar 23 Vacation 25 Vacation
Mar 30 VLSI Model I 1 VLSI Model II
Apr 6 Parallel Computation I 8 Parallel Computation II
Apr 13 Parallel Complexity Classes 15 Randomized Computation
Apr 20 Interactive Proofs I 22 Interactive Proofs II
Apr 27 Interactive Proofs III 29 Probabilistically Checkable Proofs I
May 4 Review  
21-Jan-09, Wed Overview of the Course
Serial and Parallel Models of Computation
Languages, Grammars, Machines
Time, Space and Other Resource Limitations
Properties of Models
Complexity Classifications
Reductions and their Applications
Languages Complete for a Class
Approximation Algorithms
Interactive Proofs
Tentative course schedule
Return to top
27-Jan-09, Mon Models of Computation
Problem Denitions
Models of Computation
FSM Language Recognition
TM Language Recognition
The Classes P and NP
NP-complete Languages
Return to top
29-Feb-09, Wed Classes P and NP
The classes P and NP
NP-complete languages
Proof that CIRCUIT SAT is NP-complete
Return to top
02-Feb-09, Mon NP-Complete Languages (Additional NP-Complete Languages)

NAESAT is NP-complete
0-1 INTEGER PROGRAMMING is NP-complete
INDEPENDENT SET is NP-complete
CLIQUE is NP-complete
Return to top
04-Feb-09, Wed Space Complexity
Complexity Classes
Proper Resource Bounds
Hierarchy Theorems
Savitch's Theorem
Return to top
9-Feb-09, Mon Complements of Complexity Classes
Review of Space Complexity
Complements of Complexity Classes
coNP
Polynomial Time Hierarchy
Return to top
11-Feb-09, Wed PSPACE-Complete Languages
Complexity Class Containment
Polynomial Hierarchy
PH-Complete Problems
Games and TQBF
TQBF is PSPACE-Complete
Return to top
18-Feb-09, Wed Diagonalization and Reduction
A First Application of Diagonalization
Halting is Undecidable
Resource-Bounded Reductions
Logspace Reductions
Hard and Complete Problems
Return to top
23-Feb-09, Mon Diagonalization
Time Hierarchy Theorem
Oracle Turing Machines
Under Relativization Both P = NP and PNP
Return to top
25-Feb-09, Wed Circuits
Circuit Complexity Measures
Fan-Out vs Circuit Size
Changing the Basis of a Circuit
Separator Theorem for Trees
Formula Size Versus Depth
Circuit Families
Return to top
2-Mar-09, Mon Circuits
Formula Size Versus Depth
Circuit Families
Circuit Size for Most Boolean Functions
Simple Circuit Size Lower Bounds
The Gate Elimination Method
Return to top
04-Mar-09, Wed Formula Size
Circuit Families and Simple Linear Lower Bound
The Gate Elimination Method
Neciporuk's Formula Size Lower Bound
Return to top
9-Mar-09, Mon Space-Time Tradeoffs I
The Pebble Game
Pebbling the Tree and Pyramid Graph
Extreme Tradeoffs
Return to top
11-Mar-09, Wed Space-Time Tradeoffs II
Grigoryiev Lower Bound Method for Space-Time Tradeoffs
Application to Matrix Multiplication
Return to top
16-Mar-09, Mon Space-Time Tradeoffs III
Space-Time Bounds for Convolution
Space-Time Bounds for Shifting
Return to top
30-Mar-09, Mon VLSI Model I
Definition of the VLSI model
Examples of VLSI architectures
Derivation of area-time tradeoff theorems
Planar circuit complexity
Return to top
01-Apr-09, Wed VLSI Model II
Application of the planar separator theorem
Lower bounds on AT^2 in terms of the planar complexity of functions
Return to top
06-Apr-09, Mon Parallel Computation I
Parallel models of computation
Embedding graphs
Algorithms on meshes and hypercubes
Return to top
08-Apr-09, Wed Parallel Computation II
Prefix Computations
Cyclic shift on hypercubes
Shuffle operations on linear and 2D arrays
Routing in networks
Return to top
13-Apr-09, Mon Parallel Complexity Classes
Turing Machines and Complexity
Parallel Models of Computation
The PRAM and Complexity Classes
Circuits and Complexity Classes NC and P/poly
Return to top
15-Apr-09, Wed Randomized Computation
Randomized algorithms
Average case complexity
Bounded-error complexity classes
Identity and Primality testing
Return to top
20-Apr-09, Mon Interactive Proofs I
Randomized Reductions
Two- and Three-Stage Proofs
Interactive Proofs and IP
Return to top
22-Apr-09, Wed Interactive Proofs II
Interactive Proofs
Private versus Public Randomness
Bounding the Prover's Resources
Return to top
27-Apr-09, Mon Interactive Proofs IIII
Interactive Proofs
One-way functions
Zero-Knowledge Proofs
IP and PSPACE
The Power of Interactive Proofs
Probabilistically Checkable Proofs
Return to top
29-Apr-09, Wed Probabilistically Checkable Proofs I
Probabilistically Checkable Proofs
Gap Introducing Reductions
Hardness of Approximation
Inapproximability of 3SAT
Return to top
4-May-09, Mon Review

Return to top


Home Courses