Instructor:

• Anna Karlin
  • Office: Sieg 426C
  • Email address: karlin@cs.washington.edu

Administrivia:

• Time: TTh 12:00-1:20
• Place: MEB 102
• Units: 3

Course Content:

This course will cover several applications of (linear) algebra in the design and analysis of algoreithms. Topics are likely to include:

• linear programming duality theory, and the primal/dual method for approximation algorithms
• spectral graph theory and applications
• coding theory.

Notes, etc.:

• A survey of spectral graph algorithms by Noga Alon
• 2/8/2001 Notes by Bill Pentney
• 2/13/2001 Notes by Brian Tjaden

Suggestions for papers to present:

Related to primal/dual method, linear programming duality and game theory:

• A primal-dual schema based approximation algorithm for the element connectivity problem, Kamal Jain, Ion Mandoiu, Vijay Vazirani, David Williamson. Appeared in SODA '99, pp. 484-489.
• A Primal-Dual Interpretation of Two 2-Approximation Algorithms for the Feedback Vertex Set Problem in Undirected Graphs, Fabian Chudak, Michel Goemans, Dorit Hochbaum, David Williamson. Operations Research Letters, 22:111-118, 1998. 
• E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science}, pages 404--413, Trier, Germany, 4--6 March 1999. postscript

Related to spectral graph theory:

• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
  Alistair Sinclair, Combinatorics, Probability and Computing 1 (1992), pp. 351-370

  Quick Approximation to matrices and applications (ps) by Alan Frieze and Ravi Kannan

  H. van der Holst, L. Lovász and A. Schrijver:

  The Colin de Verdi\`ere graph parameter [in: Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., 7, Janos Bolyai Math. Soc., Budapest, 1999, 29--85.] postscript

  N. Alon and N. Kahale. A spectral technique for coloring random 3-colorable graphs, STOC 1994, to appear SIAM Journal on Computing.

  N. Alon, M. Krivilevich and B. Sudakov, "Finding a large hidden clique in a random graph," SODA 1998.

  R. Boppana, "Eigenvalues and graph bisection: An average case analysis." FOCS 1987.

  Z. Furedi and J. Komlos, "The eigenvalues of random symmetric matrices", Combinatorica 1, 1981, 233-- 241.

  J. Friedman, J. Kahn and E. Szemeredi, "On the second eigenvalue in random regular graphs," STOC 1989.

Grading:

Each student will be expected to do problems, scribe a lecture, present a paper and attempt to come up with open problems. There will be no exams.