Spectral Algorithms (Fall 2007)

Tentative schedule

Tue, Aug 21: Intro/overview.

Thu, Aug 23: SVD basics, a geometric characterization.

Aug 28, 30, Sep 4. App 1: Mixture Models

Sep 6. Algo 1: Matrix multiplication

Sep 11. Algo 2: Linear-time low-rank approximation

Sep 13. Algo 3: Constant-time low-rank approximation

Sep 18. Algo 4: The CUR decomposition. HW1 to be turned in

Sep 20. App 2: Adaptive Sampling

Sep 25: Algo 5: Volume sampling

Sep 27: Algo 6: Projective Clustering. Projects finalized.

Oct 2: App 3: Isotropic Random Projection

Oct 11,16 App 4: Spectral Partitioning

Oct 23, 25. App 5: Spectral Clustering.

Oct 30. App 6: Nullspace Embeddings

Nov 1. App 7: Planar graph partitioning.

Nov 6, 8: Algorithmic Convex Geometry workshop.

Nov 13,15. App 8: Planted cliques and partitions.

Nov 20. Algo 7, App 9: Tensor Decomposition. HW3 turned in.

Nov 22. Thanksgiving

Nov 27. App 10: The regularity partition

Nov 29, Dec 4. Project reviews

Dec 6. Future directions