|
Wednesday 1/24/07 |
Complexity
Classes I: (pdf)
|
|
Monday 1/29/07 | Complexity Classes II: (pdf)
|
|
Wednesday 1/31/07 |
Complexity Classes IV:
NP Optimization Problems and Probabilistically Checkable Proofs (PCPs) (pdf)
|
|
Monday 2/5/07 |
Complexity Classes V: More PCPs
| |
Wednesday 2/7/07 |
Complexity Classes VI: Expanders and
The PCP Theorem
Asgn 1 due |
|
Monday 2/12/07 |
Complexity Classes VII: Interactive Proofs
|
|
Wednesday 2/14/07 |
Complexity Classes VIII: Stronger Approximation
Bounds
|
|
Monday 2/19/07 | Long Weekend | |
Wednesday 2/21/07 | Circuit
Complexity I (pdf)
| |
Monday 2/26/07 | Circuit
Complexity II (pdf)
|
|
Wednesday 2/28/07 |
Circuit Complexity
III (pdf)
|
|
Monday 3/5/07 | Circuit
Complexity IV (pdf)
|
|
Wednesday 3/7/07 | Space-Time
Tradeoffs II (pdf):
|
|
Thursday 3/8/07 |
Space-Time
Tradeoffs III (pdf):
|
|
Monday 3/19/07 |
Memory
Hierarchies I (pdf):
I/O-time relationships | |
Wednesday 3/21/07 |
Memory
Hierarchies II (pdf):
|
|
Thursday 3/22/07 |
Memory
Hierarchies III (pdf):
|
|
Monday 3/26/07 | Spring Break | |
Wednesday 3/28/07 | Spring Break | |
Monday 4/2/07 | Parallel
Computation II (pdf):
|
|
Wednesday 4/4/07 | Parallel
Computation III (pdf):
|
|
Monday 4/9/07 | Parallel
Computation IV (pdf):
|
|
Wednesday 4/11/07 | Parallel Complexity
Classes (pdf):
|
|
Monday 4/16/07 | The
VLSI Model I (pdf):
|
|
Wednesday 4/18/07 | The VLSI Model
III (pdf):
|
|
Monday 4/23/07 | The
VLSI Model IV (pdf):
|
|
Wednesday 4/25/07 | The
VLSI Model V (pdf):
|
|
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 |