CS256
Home Course Info Assignments Syllabus and Lectures Staff and Hours LaTeX Newsgroup

Wednesday 1/24/07 Complexity Classes I: (pdf)
  • Languages and their complements
  • Resource bounds
  • Machine models
  • Space and time complexity classes
  • Hierarchy theorems
Monday 1/29/07 Complexity Classes II: (pdf)
  • Savitch's Theorem - NSPACE(r(n)) contained in SPACE(r^2(n))
  • Relationships between complexity classes
Complexity Classes III: (pdf)
  • Complete problems for P and NP
  • The boundary between P and NP
Wednesday 1/31/07 Complexity Classes IV: NP Optimization Problems and Probabilistically Checkable Proofs (PCPs) (pdf)
  • NP Optimization Problems and Gap Preserving Reductions
  • The PCP theorem
  • A Simple Hardness of Approximation Result
Asgn 1
Monday 2/5/07 Complexity Classes V: More PCPs
  • More Hardness Results
  • Constant Factor Hardness of SAT and 3SAT
  • A Stronger Result for CLIQUE
Wednesday 2/7/07 Complexity Classes VI: Expanders and The PCP Theorem
  • Expander graphs
  • Conserving Random Bits
  • Proof of PCP theorem

Asgn 1 due

Monday 2/12/07 Complexity Classes VII: Interactive Proofs
  • Introduction to Interactive Proofs
  • IP = PSPACE
  • The Parallel Repetition Theorem
Asgn 2
Wednesday 2/14/07 Complexity Classes VIII: Stronger Approximation Bounds
  • 7/8-approximation for SAT is tight
  • Three query PCPs
  • Two query PCPs and The Unique Games Conjecture
Monday 2/19/07 Long Weekend
Wednesday 2/21/07 Circuit Complexity I (pdf)
  • Relationships between complexity measures
  • Effect of change in fan-out and basis
  • Formula size versus circuit depth
Monday 2/26/07 Circuit Complexity II (pdf)
  • Simple circuit size lower bounds 
  • The circuit size of most Boolean functions
  • The Gate Elimination Method 
Asgn 2 due
Wednesday 2/28/07 Circuit Complexity III (pdf)
  • Lower bounds for formula size 
  • Lower bounds for monotone functions
  • The path replacement method 
Asgn 3
Monday 3/5/07 Circuit Complexity IV (pdf)
  • Slice functions
Space-Time Tradeoffs I (pdf)
  • The red pebble game and extreme tradeoffs
Asgn 3 due
Wednesday 3/7/07 Space-Time Tradeoffs II (pdf)
  • Grigoriev's lower bound method
  • Space-Time Lower bounds to Convolution and Cyclic Shifting 
Thursday 3/8/07 Space-Time Tradeoffs III (pdf):
  • Space-time lower bounds for matrix multiplication
Monday 3/19/07 Memory Hierarchies I (pdf):
  • Balancing I/O and computation
  • The red-blue pebble game

  • I/O-time relationships 
Wednesday 3/21/07 Memory Hierarchies II (pdf):
  • Application of Hong-Kung Bound to Matrix Multiplication
Thursday 3/22/07 Memory Hierarchies III (pdf):
    I/O tradeoffs for the FFT
Parallel Computation I (pdf):
  • Machine and network models
  • Multidimensional mesh models
  • Matrix multiplication on meshes 
Monday 3/26/07 Spring Break
Wednesday 3/28/07 Spring Break
Monday 4/2/07 Parallel Computation II (pdf):
  • Hypercube-based machines: embedding meshes in hypercubes
  • Cube-connected cycles (CCCs) and normal algorithms
  • Summing, broadcasting, and shifting on hypercubes 
Wednesday 4/4/07 Parallel Computation III (pdf):
  • Hypercube-Based Machines
  • Shuffle and unshuffle on linear arrays
  • Normal algorithms on 2D arrays
  • Routing on networks
  • The PRAM Model
Monday 4/9/07 Parallel Computation IV (pdf):
  • PRAM
  • Work-time framework for parallel algorithms
  • Finding roots of trees in a forest
  • Parallel merging
  • Sorting
  • Simulating CREW on EREW PRAM
Wednesday 4/11/07 Parallel Complexity Classes (pdf):
  • Uniform circuit families
  • Equivalence between Turing machines and uniform circuit families
  • Equivalence between CREW PRAMs and circuits
  • The Parallel Computation Thesis 
Asgn 5 due
Monday 4/16/07 The VLSI Model I (pdf):
  • The VLSI physical and computational models
  • Layout of Trees, Meshes and the CCC 
The VLSI Model II (pdf):
  • Methods for developing area-time tradeoffs using simulations of a VLSI Chip by planar circuits
Asgn 5 
Wednesday 4/18/07 The VLSI Model III (pdf):
  • Start of the Planar Separator Theorem 
Monday 4/23/07 The VLSI Model IV (pdf): 
  • Completion of the Planar Separator Theorem 
Wednesday 4/25/07 The VLSI Model V (pdf): 
  • Lower Bounds on Planar Circuit Size and Area-Time Bounds in the VLSI Model 
Monday 4/30/07 Quantum Computing (pdf): 
Wednesday 5/2/07 Quantum Computing II
Monday 5/7/07 Take-home Final Exam out
Monday 5/14/07 Final Exam due
HomeCourses