- Anna Karlin
- Office: Sieg 426C
- Email address: firstname.lastname@example.org
- 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.
- 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.