## Instructor:

Anna Karlin

- Office: Sieg 426C
Email address:karlin@cs.washington.edu

## Administrivia:

Time:TTh 12:00-1:20Place:MEB 102Units: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.In16th 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.