Algorithmic Aspects of Machine Learning

Jerrum, M., and A. Sinclaire. “Approximating the Permanent.” SIAM Journal on Computing 18 (1989): 1149-1178.

This is the original Jerrum-Sinclair paper on approximating the permanent. I looked for a nice textbook writeup or set of lecture notes for the result, but this paper is so beautifully written that I think it’s still the best place to read about the result. We’ll only cover pp. 1149-1160 (in the journal’s page numbers).

Motwani, Rajeev, and Prabhakar Raghavan. Randomized Algorithms . Cambridge, UK: Cambridge University Press, 1995. ISBN: 9780521474658. See section 11.3. This is the section of Motwani and Raghavan’s book “ Randomized Algorithms .” that covers approximating the permanent.

Lovasz, L., and M. Simonovits. “The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume.” Foundations of Computer Science 1 (1990): 346-354.

Demmel, James W. “The Probability that a Numerical Analysis Problem is Difficult.” Mathematics of Computation 50, no. 182 (April 1988): 449-480.

Edelman, Alan. “Eigenvalues and Condition Numbers of Random Matrices.” SIAM J. Matrix Anal. Appl 9, no. 4 (1988): 543-560.

Szarek, Stanislaw J. “Spaces with Large Distance to l^n_inf and Random Matrices.” American Journal of Mathematics 112, no. 6 (Dec 1990): 899-942.

Geman, Stuart. “A Limit Theorem for the Norm of Random Matrices.” Annals of Probability 8, no. 2 (April 1980): 252-261.

Szarek, Stanislaw J. “Condition Numbers of Random Matrices.” Journal of Complexity 7, no. 2 (June 1991): 131-149.

Kahn, Jeff, Janos Komlos, and Endre Szemeredi. “On the Probability that a Random +/- 1 Matrix is Singular.” Journal of the American Mathematical Society 8, no. 1 (January 1955): 223-240.

Golub, Gene H., and Charles F. Van Loan. “Theorem 3.4.3.” Chapter 3 in Matrix Compuations. 3rd ed. Baltimore and London: The Johns Hopkins University Press, November 1, 1996, section 4.

Wilkinson, J. H. “Error Analysis of Direct Methods of Matrix Inversion.” Journal of the ACM 8, no. 3 (July 1961): 281-330.

Turner, Jonathan S. “On the Probable Performance of Heuristics for Bandwidth Minimization.” SIAM Journal on Computing 15, no. 2 (May 1986).

“Generalized Nested Dissection.” SIAM Journal on Numerical Analysis 16 (1979): 346-358.

LEC #: 7 · TOPICS: Spectral Partitioning Introduced · READINGS: “Spectral Partitioning Works: Planar Graphs and Finite-Element Meshes.” Proceedings of the 35th Annual IEEE Conference on Foundations of Computer Science. 1996, pp. 96-105.

LEC #: 8 · TOPICS: Spectral Partitioning of Planar Graphs · READINGS: “Spectral Partitioning Works: Planar Graphs and Finite-Element Meshes.” Proceedings of the 35th Annual IEEE Conference on Foundations of Computer Science. 1996, pp. 96-105.

Miller, Gary L., Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. “Separators for Sphere-Packings and Nearest Neighbor Graphs.” Journal of the ACM 44, no. 1 (January 1997): 1-29.

———. “Geometric Separators for Finite Element Meshes.” Siam Journal on Scientific Computing 19, no. 2 (March 1998): 364-386.

Feige, Uri, and Joe Kilian. “Heuristics for Semirandom Graph Problems.” Journal of Computer and System Sciences. ———. “Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.” Proceedings of 39th FOCS. 1998, pp. 674-683. Available at Uri Feige’s homepage.

Boppana, Ravi . “Eigenvalues and Graph Bisection: an Average-Case Analysis.” Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 280-285, IEEE Computer Society Press, 1987.

Johnson, D. S., C. R. Aragon, L. A. McGeoch, and C. Shevon. “Optimization by Simulated Annealing: an Experimental Evaluation. Part I, Graph Partitioning.” Operations Research 37, no. 6 (1989): 865-892.

“Spectral Partitioning of Random Graphs.” 42nd IEEE Symposium on Foundations of Computer Science Proceedings: October 14–17, 2001. Las Vegas, Nevada, USA: IEEE Computer Society Press, 2001, pp. 529-537. Frank McSherry’s analysis of a spectral partitioning algorithm for the planted bisection model.

Amenta, Nina, and Gunter Ziegler. “Deformed Products and Maximal Shadows of Polytopes.” Advances in Discrete and Computational Geometry. Edited by B. Chazelle, J. E. Goodman, R. Pollack. Vol. 223, Contemporary Mathematics. Providence, R.I.: Amer. Math. Soc., 1999, pp. 57-90. ISBN: 0821806742.

Ziegler, Günter M. Lectures on Polytopes . New York: Springer-Verlag, 1995.

LEC #: 15 · TOPICS: The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane · READINGS: Uber die convexe hulle von is zufallig gewahlten punkten, I and II. Z. Whar. 2, 75-84; 3, 138-148. (1963; 1964).

LEC #: 16 · TOPICS: The Expected Number of Facets of the Convex Hull of Gaussian Random Points in the Plane (cont.) · READINGS: Uber die convexe hulle von is zufallig gewahlten punkten, I and II. Z. Whar. 2, 75-84; 3, 138-148. (1963; 1964).

LEC #: 18 · TOPICS: The Expected Number of Facets of the Shadow of a polytope Given by Gaussian Random Constraints: Distance Bound · READINGS: Spielman (cont.)

LEC #: 19 · TOPICS: The Expected Number of Facets of the Shadow of a Polytope Given by Gaussian Random Constraints: Angle Bound and Overview of Phase 1 · READINGS: Spielman (cont.)