The following is an approximate list of topics covered in CMSC 651, Spring 2018.

This is an approximate summary, but gives an idea of the primary issues covered. Please let Aravind know if there are any major omissions or errors.

Lecture 1, Jan. 25, 2018:

• Our first topic: randomized algorithms and the probabilistic analysis of algorithms.
• A simple example: checking polynomial equalities, and an optimal lower bound for deterministic algorithms (see Lecture 1 in the lecture notes).
• The basic model of random sources for randomized algorithms; von Neumann's trick in the case of unknown bias (but assuming independence).
• Basics of probability including mutual exclusion and independence; the union bound and the alternating properties of truncated inclusion-exclusion (see Lecture 4 in the lecture notes).
• Conditional probability and "exposure" arguments.
• A second example of fast algorithms using randomization: Freivalds' algorithm to verify matrix multiplication.
• Required Reading: Lectures 1 and 2 from the lecture notes.

• The Principle of Deferred Decisions.
• Randomized algorithms vs. the probabilistic analysis of algorithms.
• Bayesian reasoning: how does our belief evolve as we run iterations of Freivalds' algorithm?
• A Naive Bayes Classifier, conditional independence, and a very brief discussion of graphical models.
• More on conditioning and deferred decisions: start the Isolation Lemma.

• Finish the proof of the Isolation Lemma.
• The matching problem, its classical and continuing roles, and the application of the Isolation Lemma to matching, due to Mulmuley-Vazirani-Vazirani.
• Proofs for the linearity of expectation and the expectation of a product of independent random variables.
• Alternative formula for the expectation, and application to the Negative Binomial distribution.
• Applications of the linearity of expectation: a randomly-typing monkey generating profound statements, and coupon collector.
• Required Reading: Ta-Shma's proof of the Isolation Lemma.

• Markov's inequality; careful iterated application to converting Las Vegas algorithms such as Randomized Quicksort to high-probability schemes.
• The "+1/-1" trick and an unbiased estimator for the permanent: why tail bounds are needed, and why we minimally need variance bounds.
• Use of Chebyshev for basic sampling; also cover sampling without replacement and how negative correlation helps.
• Algorithms and the future of jobs?
• Start Chernoff-Hoeffding.

• Proof for Chernoff-Hoeffding, and the behavior of the bounds in various regimes.
• How Chernoff-Hoeffding gets improved sampling bounds.
• An introduction to k-wise independence (e.g., discussion of a simple pseudorandom generator that stretches t random bits to 2^t - 1 unbiased and pairwise independent random bits), and connections to sampling.

• An unsuccessful attempt to apply the Chernoff approach to the upper-tail of Coupon Collector. (Student Leonidas Tsepenekas later came up with an elegant upper-bound; the notes I distributed show why this upper bound is tight. HW2 shows that the lower tail of Coupon Collector decays rapidly, via correlation inequalities.)

• The data-stream model and the Alon-Matias-Szegedy upper-bound for estimating F_2.
• A useful statistical tool: the median-of-means estimator.
• Start decision problems, Turing machines and computational complexity.

• The complexity classes P, NP, coNP, PSPACE and EXPTIME: inclusions and conjectures.
• Reductions, NP-completeness, and the Cook-Levin Theorem.
• The status and importance of the P vs. NP problem; the legacies of Cook, Edmonds, Karp, Levin, Nash, and Turing.
• Brief discussion of PPAD and #P.
• Reduction from 3-SAT to INDEP. SET.
• Computational complexity as a lens on the sciences.
• Start the notion of an approximation algorithm.

• Recap the notion of an approximation algorithm.
• The set-cover problem: integer-programming formulation, linear programming (LP) in general and its geometry, and LP-relaxation for set cover.
• Some insight into the computational aspects of LP and convex programming:
  • convex programming and its history, "separation" as equivalent to optimization, and basic properties of gradients;
  • the performance of gradient descent (a basic local-search technique) for convex optimization (with bounded gradients and diameter), from the first 25 minutes of Elad Hazan's video.
• randomized rounding for set cover: a slightly-different approach and proof than in Williamson-Shmoys.
• Required Reading: Chapter 1 of Williamson-Shmoys, and at least the first 25 minutes of Elad Hazan's video.

• Section 2.1 of Williamson-Shmoys.
• Most of Section 2.2 of Williamson-Shmoys.

• Complete Section 2.2 from Williamson-Shmoys.
• Section 2.3 of Williamson-Shmoys.
• Very quick recap of dynamic programming.
• Matrix powering for linear recurrences: much-faster algorithms compared to naive dynamic programming.
• Color coding for finding long simple paths: elegant randomization plus dynamic programming.
• Start Section 3.1 of Williamson-Shmoys: introduction to knapsack and to the notion of an FPTAS.
• Required Reading: Section of 3 of the very-useful Alon-Yuster-Zwick paper on color-coding.

• Complete Section 3.1 from Williamson-Shmoys.
• Pseudo- and strongly-polynomial-time algorithms, does LP have a strongly-polynomial algorithm?, and Tardos' work on strong polynomiality for LPs such as min-cost flow.
• LP-rounding for knapsack, and the associated linear-algebraic methods.
• Finish Section 3.2 from Williamson-Shmoys.

• Section 4.2 from Williamson-Shmoys.
• Recap of the computational equivalence of separation and optimization, and high-level coverage of Section 4.3 from Williamson-Shmoys.
• Section 6.1 from Williamson-Shmoys.

• Section 6.2 from Williamson-Shmoys.
• Some useful facts: why the high-dimensional Gaussian is what models the uniform distribution on the sphere, conic combinations, and the PSD cone.
• High-level coverage of Section 6.3 from Williamson-Shmoys.

• The PRAM models, and the complexity classes NC^i, RNC^i, NC, and RNC.
• A few basic divide-and-conquer algorithms on the PRAM.
• An interlude motivated by such divide-and-conquer: for what functions f(n) does the recurrence T(n) = T(f(n)) + O(1) solve to T(n) = O(log n), O(log log n), O(log log log n) etc.?
• P-completeness and the distinction between two related problems: matching and flow.

• Quick recap of the PRAM model.
• Quick overview of MapReduce from the work of Karloff-Suri-Vassilvitskii.
• Matroids: examples and proof of optimality of the greedy algorithm.
• The rank function of matroids and the statement alone of its submodularity.

• Submodularity: two equivalent definitions, examples, and statement alone of Lovasz's result about minimizing a submodular function.
• Proof of submodularity of the matroid rank function.
• The matroid polytope and its separation oracle.
• The tight constraints at a vertex of a polytope span the ambient space.

• Online algorithms and the competitive ratio.
• Internet advertising and online algorithms.
• The Karp-Vazirani-Vazirani algorithm for online bipartite matching, and primal-dual analysis due to Devanur-Jain-Kleinberg.

• The tight constraints at a vertex of a polytope span the ambient space.
• Structure of tight constraints at a vertex of a matroid polytope, using the key technique of uncrossing; an (optional) "\ell_2^2" potential technique to see why uncrossing converges.
• The integrality of the matroid polytope.
• Start matroid intersection.
• Required Reading: Proofs (using uncrossing) of Lemmas 4.1.5 and 5.2.3 from Lau-Ravi-Singh.

• Matroid intersection: e.g., bipartite matching and max-weight arboresence.
• Proof of integrality for matroid intersection.
• Shortest paths as an introduction to flow:
  • Shortest path as min-cost unit flow.
  • Edge-based and path-based flows; flow decomposition.
  • LP formulation and integrality.
• Max flow: definition, residual graph and augmenting paths, Ford-Fulkerson algorithm, short discussion about Fulkerson.
• Required Reading: Chandra Chekuri's two slide-decks: here and here.

• Max flow:
  • Residual graphs and augmenting paths
  • Convergence and optimality of the Ford-Fulkerson algorithm
  • The max-flow min-cut theorem
  • Time complexity of max-flow from Ford-Fulkerson, Edmonds-Karp, and various improvements to Lee-Sidford
  • Brief discussion of: Tardos' strongly-polynomial-time algorithm for min-cost max flow, the modern interior-point methods, and Karp's fireside chat (interview with Samir Khuller) quip about the modern role of linear algebra
• Recap of duality; weak and strong duality
• Dual relationship between max-flow and min-cut; integrality of the min-cut relaxation
• Required Reading: Chandra Chekuri's two slide-decks: here and here.
• Recommended Viewing: Richard Karp's fireside chat with Samir Khuller

• Pipage rounding and its randomized counterpart, dependent rounding:
  • Applications to max-k-coverage.
  • Fairness in algorithms and machine learning, a possible formulation of fairness in k-coverage, dependent rounding for fair k-coverage, and verifiable fairness.
  • Dependent-rounding algorithm and proofs of its properties (especially the negative cylinder property -- property (A3) in the dependent rounding paper).
• Required Reading: The algorithm and proofs of properties (A1), (A2), and (A3) from the dependent rounding paper.
• Recommended reading about a very key issue: The resources on Fairness, Accountability, and Transparency in Machine Learning at FAT/ML.

• Recap of basic linear algebra, including:
  • subspaces and dimension;
  • orthonormal bases;
  • basis rotation and the \ell_2 norm;
  • the \ell_2 norm and sums of squares (as opposed to other powers), and how these enable the Pythagoras Theorem, eigenvalues, basis rotation etc.;
  • length, dot product, projection onto a vector and onto a subspace;
  • matrix rank and proof of its subadditivity.
• Discussion of the work of Jon Kleinberg, specifically the pre-history of web-search and very brief coverage of Kleinberg's linear-algebraic work, as well as modern ML combined with human decisions for bail cases.
• Start SVD from Chapter 3 of Blum-Hopcroft-Kannan:
  • data as an n x d matrix, but often low-rank or close to low rank;
  • want: a k-dim subspace that minimizes the sum of the squares of the projection distances or equivalently, maximizes the sum of the squares of the lengths of the projections;
  • the case k = 1 and the first singular value (the spectral norm);
  • the inductive greedy algorithm for higher singular vectors, and when this process stops.
• Recommended Viewing: Eric Horvitz's fireside chat with Jon Kleinberg.

• Continue with SVD from Blum-Hopcroft-Kannan.
• The SVD algorithm and proof of correctness.
• The right singular vectors are a basis for the row-space of the matrix.
• Perspective on how changing the basis carefully can help (and brief mention of a different approach that shares this feature in some cases: Fourier analysis).
• The Frobenius norm and the sum of the squares of the singular values.
• Optional Reading: The power of linear-algebraic (e.g., vector) embeddings in automatically learning associations: see Mikolov-Yih-Zweig.

• The SVD decomposition into the sum of rank-one matrices.
• How to get the best rank-k approximation in terms of Frobenius distance.
• The left-singular vectors and why they are orthogonal.
• What happens when the matrix is symmetric?

• The power method and its applications.
• Two cool, surprising proofs using the linearity of expectation:
  • Mehtaab Sawhney's recent proof reducing the triangle inequality in high dimension to dimension one.
  • Buffon's noodle: statement alone.
• Quick recap of the topics after the mid-term, and discussion of the final exam.

• Recap of the class.

Web Accessibility