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 P ≠ NP
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
|