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

Calendar Month Tue Thu Jan   24 Review and Overview Jan 29 Models of Computation   Month Mon Wed Fri Feb     1 Classes P and NP Feb 4 NP-Complete Languages 6 NP-Complete Languages 8 NP-Complete Languages Feb 11 Space Complexity 13 Complements of Classes   Feb 18 Holiday 20 PSPACE-Complete Languages 22 Diagonalization Feb 25 Diagonalization 27 Circuits 29 Circuits Mar 3 Circuits 5 Formula Size   Mar 10 Space-Time Tradeoffs I 12 Space-Time Tradeoffs II 14 Space-Time Tradeoffs III Mar 17 VLSI Model I 18 VLSI Model II 19 VLSI Model III Mar 31 Parallel Computation I 2 Parallel Computation II 4 Parallel Computation III Apr 7 Parallel Complexity Classes 9 Randomized Computation 11 Randomized Computation II Apr 14 Interactive Proofs 16 Interactive Proofs II 18 Interactive Proofs III Apr 21 Interactive Proofs IV 23 Interactive Proofs V 25 Interactive Proofs VI Apr 28 Probabilistically Checkable Proofs I 30 Probabilistically Checkable Proofs II 02 Probabilistically Checkable Proofs III 24-Jan-08, Thu Review and Overview 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 Tentative course schedule Return to top 29-Jan-08, Tue Models of Computation Problems and Languages Circuits, Finite State Machines, Turing Machines Determinism and Nondeterminism, Language Recognition The classes P and NP NP-complete Languages Return to top 01-Feb-08, Fri Classes P and NP The classes P and NP How to show languages are in P and NP. Return to top 04-Feb-08, Mon NP-Complete Languages A First NP-Complete Language Proof that CIRCUIT SAT is NP-complete Showing that a New Language is NP-complete Return to top 06-Feb-08, Wed 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 08-Feb-08, Fri NP-Complete Languages VERTEX COVER is NP-Complete SUBSET SUM is NP-Complete PARTITION is NP-Complete Return to top 11-Feb-08, Mon Polynomial Space Complexity Classes Proper Resource Bounds Hierarchy Theorems Savitch's Theorem Return to top 13-Feb-08, Wed Complements of Complexity Classes Complements of Complexity Classes coNP Polynomial Time Hierarchy Return to top 20-Feb-08, Wed PSPACE-Complete Languages Complexity Class Containment Polynomial Hierarchy PH Games and TQBF TQBF is PSPACE-Complete Return to top 22-Feb-08, Fri Diagonalization A First Application of Diagonalization Halting is Undecidable Resource-Bounded Reductions Logspace Reductions Hard and Complete Problems Return to top 25-Feb-08, Mon Diagonalization Time Hierarchy Theorem Oracle Turing Machines Under Relativization Both P = NP and P ≠ NP Return to top 27-Feb-08, 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 29-Feb-08, Fri 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 03-Mar-08, Mon Circuits Circuit Families and Simple Linear Lower Bound The Gate Elimination Method Neciporuk's Formula Size Lower Bound Return to top 05-Mar-08, Wed Formula Size Application of Neciporuk's Formula Size Lower Bound Krapchenko's Formula Size Lower Bound Return to top 10-Mar-08, Mon Space-Time Tradeoffs I The Pebble Game Pebbling the Tree and Pyramid Graph Extreme Tradeoffs Return to top 12-Mar-08, Wed Space-Time Tradeoffs II Grigoryiev Lower Bound Method for Space-Time Tradeoffs Application to Matrix Multiplication Return to top 14-Mar-08, Fri Space-Time Tradeoffs III Space-Time Bounds for Convolution Space-Time Bounds for Shifting Return to top 17-Mar-08, Mon VLSI Model I Definition of the VLSI model Examples of VLSI architectures Return to top 18-Mar-08, Tue VLSI Model II Derivation of area-time tradeoff theorems Planar circuit complexity Return to top 19-Mar-08, Wed VLSI Model III Application of the planar separator theorem Lower bounds on AT^2 in terms of the planar complexity of functions Return to top 31-Mar-08, Mon Parallel Computation I Parallel models of computation Embedding graphs Algorithms on meshes and hypercubes Return to top 02-Apr-08, Wed Parallel Computation II Cyclic shift on hypercubes Shuffle operations on linear and 2D arrays Routing in networks Return to top 04-Apr-08, Fri Parallel Computation III PRAM Model Prefix Computations The Circuit Model of Computation Return to top 07-Apr-08, Mon Parallel Complexity Classes Review of models of computation and complexity classes The PRAM and the parallel complexity class NC Circuit families and P/poly Return to top 09-Apr-08, Wed Randomized Computation Randomized algorithms Average case complexity Bounded-error complexity classes Indentity and Primality testing Return to top 11-Apr-08, Fri Randomized Computation II Relationships between ZPP, RP and BPP Error-Reduction Return to top 14-Apr-08, Mon Interactive Proofs I Randomized Reductions Interactive Protocols IP Return to top 16-Apr-08, Wed Interactive Proofs II Public verus Private Coins AM and IP Return to top 18-Apr-08, Fri Interactive Proofs III Interactive Proofs Bounding the Prover's Resources Zero-Knowledge Proofs IP and PSPACE Return to top 21-Apr-08, Mon Interactive Proofs IV Interactive Proofs One-way functions Zero-Knowledge Proofs Return to top 23-Apr-08, Wed Probabilistically Checkable Proofs The Power of Interactive Proofs Probabilistically Checkable Proofs Return to top 25-Apr-08, Fri PCP and NP PCP Gap Introducing Reductions Hardness of Approximation Return to top 28-Apr-08, Mon PCPs and Approximation PCP Gap Introducing Reductions Hardness of Approximation Return to top 30-Apr-08, Wed Hardness of Approximation Inapproximability of 3SAT Return to top 02-May-08, Fri Probabilistically Checkable Proofs V Inapproximability of CLIQUE Return to top