EECS 6118 :  Project  Info

Time Table:

Project Proposal (by the end of the 2nd month in the term) 

Final Report & Presentation (last lecture hour)

Some Past Projects:

Suggested new project topics
and reading list:
  1. J. Kelner, L. Orecchia, A. Sidford, "A Simple, Combinatorial  Algorithm for Solving SDD Systems in Nearly-Linear Time," Proc. Symposium on Theory of Computing (STOC), 2013.
  2. J. Dunagan, N. Harvey, "Iteratively Constructing Preconditioners via the Conjugate Gradient Method," STOC 2007.

  3. J. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain," 1994.
  4. C. Godsil, G. Royle, "Algebraic Graph Theory," Springer, 2001.
  5. D. Spielman, "Lecture Notes: Spectral Graph Theory," 2012.

  6. P. Christiano, J. Kelner, A. Madry, D. Spielman, S.-H. Teng, "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs," STOC 2011.
  7. S. Arora, S. Rao, U. Vazirani, "Expander Flows, Geometric Embeddings and Graph Partitioning," STOC 2004.

  8. M. Barasz, S. Vempala, "A New Approach to Strongly Polynomial Linear Programming," Innovations in Computer Science, 2010.
  9. J. Kelner, D. Spielman, "A Randomized Polynomial-Time Simplex Algorithm for Linear Programming," STOC 2005.
  10. J. Dunagan, S. Vempala, "A Simple Polynomial-time Rescaling Algorithm for Solving Linear Programs," STOC 2004.
  11. E. Tardos, "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Resaerch 34(2), pp: 250-256, 1986.
  12. E. Hazan, "Lecture Notes: Polynomial Time Algorithms for Linear Programming," 2011.

  13. S. Arora, E. Hazan, S. Kale, "The Multiplicative Weights Update Method: a Meta Algorithm and Applications,"  Journal of Theory of Computing, 2010.
  14. S. Arora, S. Kale, "A Combinatorial, Primal-Dual approach to Semidefinite Programs," STOC 2007.
  15. L. Lovasz, "Lecture Note: Semidefinite programs and combinatorial optimization,"  1995.

  16. J. Hopcroft, R. Kannan, "Computer Science Theory for the Information Age," to be published soon.