Recommended Papers

• From my own lecture notes:
  • Peron's Theorem Lect 2, '98, and connected components after spectral cuts Lect 3, '98.

  • Eigenvectors of path graphs. Theorem 5 of Lect 1, '96

  • Proving expansion from eigenvalues Lect 4, '98

  • Cheeger's inequality (cuts from eigenvectors) Lect 5, '98

• Using Eigenvectors to find structures in graphs:
  • F. McSherry Spectral Partitioning of Random Graphs. STOC '01. You can also work from my lecture notes of an easier version of this result

  • "Spectral Analysis of Data" by Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry and Jared Saia. Symposium on Theory of Computing 2001. ( ps , pdf).

  • Daniel Spielman and Shang-Hua Teng Spectral Partitioning Works: Planar graphs and finite element meshes. An extended abstract appeared in Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, 1996. You can also work from My lecture notes on this topic

  • N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms 13 (1998), 457-466.
  • N. Alon and B. Sudakov, Bipartite subgraphs and the smallest eigenvalue, Combinatorics, Probability and Computing 9 (2000), 1-12.
  • N. Alon, M. Krivelevich and V. H. Vu,
  On the concentration of eigenvalues of random symmetric matrices,
  Israel Journal of Mathematics 131 (2002), 259-267.
   
  • N. Alon and N. Kahale, A spectral technique for coloring random 3-colorable graphs, Proc. of the 26th ACM STOC, ACM Press (1994), 346-355. Also; SIAM J. Comput. 26 (1997), 1733-1748.

• Papers on predconditioners or used to create them:
  • Support-Graph Preconditioners, Marshall Bern, John R. Gilbert, Bruce Hendrickson, Nhat Nguyen and Sivan Toledo, submitted to SIAM J. Matrix Anal. & Appl.
    Paper, Abstract

  • Support Theory for Preconditioning, Erik Boman and Bruce Hendrickson, submitted to SIAM J. Matrix Anal. & Appl. (Revised 10/02)
    Paper, Abstract

  • Maximum-Weight-Basis Preconditioners, Erik Boman, Doron Chen, Bruce Hendrickson and Sivan Toledo, to appear in Numerical Linear Algebra and Applications.
    Paper, Abstract

  • N. Alon, R.M. Karp, D. Peleg, and D. West. "A graph-theoretic game and its application to the k-server problem", SIAM J. Comput., 24:1, 78--100 (1995).

• Papers on Quantum Computation
  • Title: Quantum Computation by Adiabatic Evolution
    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser
    quant-ph/0001106 [abs, ps, pdf, other]

  • Title: Adiabatic Quantum State Generation and Statistical Zero Knowledge
    Dorit Aharonov and Amnon Ta-Shma
    quant-ph/0301023 [abs, ps, pdf, other] :