Spring 2001

- 5134 Upson.
- 255-3600.

CS 683 is a new course designed to serve as an advanced follow-up to CS 681. The goal is to cover recent results and current problems, and illustrate a number of open directions of research in algorithms. The course pre-requisite is CS 681 or equivalent background in algorithms and discrete mathematics.

The course focuses on an inter-related collection of topics centered around randomization, graph decomposition, and methods from high-dimensional geometry. It concentrates on both fundamental techniques and their applications. Techniques include linear programming duality, metric embeddings, random walks, random sampling, spectral partitioning, and spectral clustering. Applications include graph partitioning and its role in approximation algorithms; heuristics for routing; approximate sampling and counting; and high-dimensional clustering and indexing.

(1) **Brief introduction to linear programming and duality.**

(2) **Graph partitioning via multicommodity flow.**

- Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM Volume 46 , No. 6 (Nov. 1999) Pages 787 - 832
- Lecture 4.
- Lecture 5.
- Lecture 6.
- Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM Volume 46 , No. 6 (Nov. 1999) Pages 787 - 832

(3) **Multicommodity flow and the sparsest cut problem.**

- H. Okamura and P.D. Seymour. Multicommodity Flows in Planar Graphs. Journal of Combinatorial Theory, Series B 31(1981), pp. 75-81.
- N. Linial, E. London and Yu. Rabinovich The geometry of graphs and some of its algorithmic applications. Combinatorica (1995) 15, pp. 215-245
- Y. Aumann and Y. Rabani. An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm. SIAM J. Comput., 27(1):291--301, February 1998. (Alternate link.)
- Lecture 7.
- Lecture 8.
- Lecture 9.
- Lecture 10.
- H. Okamura and P.D. Seymour. Multicommodity Flows in Planar Graphs. Journal of Combinatorial Theory, Series B 31(1981), pp. 75-81.

(4) **Eigenvalues and expansion.**

- N. Alon. Eigenvalues and Expanders. Combinatorica 6(1986), pp. 83-96.
- A. Sinclair and M. Jerrum. Approximate Counting, Uniform Generation, and Rapidly Mixing Markov Chains. Information and Computation 82(1989), pp. 93-133.
- Daniel A. Spielman and Shang-Hua Teng. Spectral Partitioning Works: Planar graphs and finite element meshes. Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, 1996. and UC Berkeley Technical Report number UCB CSD-96-898.
- F.R.K. Chung. Spectral Graph Theory. AMS Press. 1997.
- Lecture 11.
- Lecture 12.
- Lecture 13.
- Lecture 14.
- N. Alon. Eigenvalues and Expanders. Combinatorica 6(1986), pp. 83-96.

(5) **Random walks, rapid mixing, and approximate counting.**

- L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.
- Mark Jerrum and Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration. in Approximation Algorithms for NP-hard Problems, D.S.Hochbaum ed., PWS Publishing, Boston, 1996.
- Mark Jerrum and Alistair Sinclair. Approximating the Permanent. SIAM J. Computing 18(1989), pp. 1149-1178.
- See also Mark Jerrum, Alistair Sinclair, Eric Vigoda A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. ECCC Report TR00-079 (2000).
- Lecture 15.
- Lecture 16.
- Lecture 17.
- Lecture 18.
- L. Lovasz. Random Walks on Graphs: A Survey. Combinatorics: Paul Erdos is Eighty (vol. 2), 1996, pp. 353-398.

(6) **Random sampling and the VC-dimension.**

- D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2 (1987), 127--151.
- H. Bronnimann and M.T. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Preliminary version appeared in Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 293-302.
- J. Kleinberg. Detecting a Network Failure. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
- Lecture 19.
- Lecture 20.
- Lecture 21.
- D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2 (1987), 127--151.

(7) **High-dimensional nearest neighbor algorithms for
indexing and classification.**

- J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proc. 29th ACM Symposium on Theory of Computing, 1997.
- Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani. Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. SIAM J. Comput. 30(2): 457-474 (2000)
- P. Indyk, R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Proc. 30th ACM Symposium on Theory of Computing, 1998.
- T.M. Cover, P.E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1967), pp. 21--27.
- Lecture 22.
- Lecture 23.
- Lecture 24.
- J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proc. 29th ACM Symposium on Theory of Computing, 1997.

(8) **The singular value decomposition and high-dimensional clustering.**

- Deerwester, S., Dumais, S. T., Landauer, T. K., Furnas, G. W. and Harshman, R. A. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6), 391-407 (1990).
- J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
- S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998.
- C. H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala. Latent semantic indexing: A probabilistic analysis. ACM Principles of Database Systems, 1998.
- Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia. Spectral analysis of data. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
- P. Drineas, Ravi Kannan, Alan Frieze, Santosh Vempala and V. Vinay Clustering in large graphs and matrices. Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999.
- Lecture 25.
- Lecture 26.
- Lecture 27.
- Deerwester, S., Dumais, S. T., Landauer, T. K., Furnas, G. W. and Harshman, R. A. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6), 391-407 (1990).

The work for the course consists of four problem sets, and the periodic writing of scribe notes.