The following is an approximate list of topics covered in CMSC858C, Spring 2017.

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. 26, 2017:

• Randomized algorithms and the probabilistic analysis of algorithms: motivations to study them, their similar underlying techniques despite their different contexts.
• What is a randomized algorithm? Illustration via Karger's min-cut algorithm
• Two powerful paradigms that make Karger's algorithm work:
  • The abundance of witnesses
  • The power of random permutations
• More-formal analysis of conditioning by an exposure argument
• Spinoff of Karger's result to upper-bounds on the number of min-cuts.
• The expectation and its two interpretations ("long-term average" and "probabilistic method") that will be of use to us; expectation vs. median; the linearity of expectation.
• An elegant application of random permutations and the linearity of expectation to show Turan's Theorem on independent sets.

• The probabilistic method, a close relative of randomized algorithms: a first taste via large cuts in graphs, improvement based on sampling without replacement, and the overall philosophy of useful (smaller/better) sample spaces that suffice for a given probabilistic analysis.
• Brief history of the probabilistic method and randomized algorithms.
• Recap of hashing; can random cuts be viewed as hashing?
• The communication complexity of Equality: upper bound, and mention of lower-bound techniques from Arora's lecture notes.
• Paradigms underlying the communication-complexity application: hashing/fingerprinting, and the abundance of witnesses.
• Brief discussion of randomized algorithms and zero-sum games.
• Required reading: Lower-bound techniques in communication complexity, from Arora's lecture notes

• Alternative formula for the expectation, its analog (via integration by parts) for continuous distributions, application to coin-flipping.
• Randomized Quicksort and two analyses; lower bound on expected run-time via Yao's theorem.
• Markov's inequality, and refined (repeated early-stopping) application of it to algorithms (such as Randomized Quicksort).
• Start Chebyshev's inequality.

• The data-stream model, and the Alon-Matias-Szegedy F_2 estimator (only the statement of this result for now) as a motivating example for the next 2-3 classes' discussion.
• Complete Chebyshev's inequality, and examples that compare it to Markov.
• Applications in sampling (and how can polling fail in practice?).
• Variance, variance of a sum, co-variance and correlation, negative correlation in sampling without replacement, the "square-root phenomenon" in tail bounds.
• Variance and pairwise independence: a quick introduction to a simple way of constructing pairwise independent, unbiased random bits

• The union bound and truncated inclusion-exclusion:
  • Picture proofs for the properties of truncated inclusion-exclusion;
  • Two ways of viewing joint distributions (exposure arguments and tree diagrams), conditioning as re-normalization.
• The basic premise of data science, and how to use (pairwise-independent) sampling and the union bound here.
• The distance traveled by the standard random walk on the integers:
  • Upper bounds through the second and fourth moment;
  • A failed attempt to lower-bound the distance using the fourth moment (why did this fail? we will fix it in the next class).
• Required reading: The Bellare-Rompel tail bounds: the theorems from Section 2 of their paper and the proof from the Appendix.
• Start the Chernoff bounds.

• Lower-bounding the distance traveled by the random walk via an one-sided bound and the fourth moment.
• Complete the basic Chernoff-Hoeffding upper- and lower- tail bounds, examine their behavior in different regimes, and cover an example where the AM-GM-based (Hoeffding) bound is better than the standard bound.
• Sampling and large-deviation bounds such as Chernoff-Hoeffding.
• The basic approach of Alon-Matias-Szegedy.

• Why are tail bounds so helpful? The paradigm of "design assuming the relevant random variables stay close to their mean, then prove the requisite tail bounds", and connections to Alon-Matias-Szegedy.
• Recap of Chernoff-Hoeffding, a peek at random graphs, why random-graph modeling, and at the to-be-seen-later fact that the upper tail for (say) triangle-count in G(n,p) is much trickier than the lower tail.
• Fixed points in permutations and the Poisson approximation (initial introduction to this approximation -- will cover in more detail later).
• Develop solutions to HW1.

• The last problem from HW1: quicker solution using symmetry, and longer solution in order to practice conditioning and recurrences (these will help with probabilistic recurrence relations later -- e.g., in randomized distributed algorithms).
• Finish Alon-Matias-Szegedy.
• Start k-wise independence via Reed-Solomon codes.

• Complete Reed-Solomon codes and k-wise independence; brief mention of other families of relevant codes.
• Perspective on Alon-Matias-Szegedy (AMS): the twin notions of small sample spaces (which had been developed from entirely-different viewpoints more than a decade before AMS) and the tight connection between probability and empirical frequency (or expectation and the sample average).
• More on viewing probability as empirical frequency: Alon-Yuster's 123 Theorem -- see Sections 1 and 2 of this paper.
• The choice m -> infinity is natural in Alon-Yuster, but also see the related, more-general tensor powering trick.
• Settings where "probability as empirical frequency" is not always appropriate: see Orlitsky-Santhanam-Zhang.
• A non-technical but vital issue for all of us: what is the future of jobs for humans, when machines can do a great deal of what humans do today? A relevant article by Brynjolfsson and McAfee, on why this is not just the "lump of labor" fallacy.

• Selecting the median via randomization.
• How good are our computers' random-number generators? General discussion for today; some rigorous approaches to this to be covered later.
• A simple construction for pairwise independence; a connection between k-wise independence and linear independence.
• Start the Gaussian approximation.

• More on the Gaussian approximation, and bounds on the Gaussian tail.
• Poisson approximation:
  • The easy case of independent rare summands.
  • Brun's Sieve (see slides 32-37 of Lu's presentation) for the case of "almost independent" rare summands as in the number of fixed points of a random permutation.
  • A useful tool for the above and more generally: how do we estimate the product (1 - 1/n) (1 - 2/n) ... (1 - k/n) for: k = o(sqrt{n})? for k = o(n^{2/3})? ... etc.
• Start the probabilistic method: some history (especially the legacy of Erdos), and Ramsey graphs.

• Solutions for HW2, the Hajnal-Szemeredi Theorem, and the useful role of dependency graphs.
• Recap of Ramsey graphs and the role of random graphs (and random structures) in existence proofs.
• Constructing Ramsey graphs in deterministic quasi-polynomial time, and the general area of explicit constructions.
• Quick coverage of binomial sums, entropy, and the relative entropy (more in the required reading below).
• Required reading: (i) Binomial sums, convexity, and the Shannon entropy from Section 1, Lecture 18 of the lecture notes; (ii) the K-L divergence and tail bounds from Section 2.2.1, Lecture 14 of the lecture notes (also see the beautiful short proof by Sanjoy Dasgupta).

• The method of alteration and its use in finding large independent sets.
• How can the above be improved upon? Add our known friend, the power of random permutations, and use Jensen's inequality to prove Turan's Theorem.
• Why do random permutations work (much) better than each edge inside the initial set I choosing one random end-point to remove?
• Alteration and random permutations fruitfully viewed as inherent to the probabilistic method
• Recap random graphs, quick overview of the "double jump".
• Using random graphs and the method of alteration to prove the existence of graphs with large girth and large chromatic number: the basic ideas covered in class, full proof can be seen here.

• Recap the power of random permutations.
• Hypergraph 2-coloring:
  • The basic problem and contrast with graph coloring.
  • The function m(k): the simple 2^{k-1} - 1 lower bound and the next small step: the 2^{k-1} lower bound.
  • Statement alone of upper bound O(k^2 2^{k}) upper bound due to Erdos, and the conjectured Theta(k 2^{k}) from one of the seminal Erdos-Lovasz papers.
  • The Radhakrishnan-Srinivasan lower bound, coverage of its simplification due to Cherkashin and Kozik.
  • The case of non-uniform hypergraphs: statements alone of the lower bounds due to Beck and due to Lu.
  • General discussion of the role that Erdos' conjectures have played: e.g., the new techniques that the study of hypergraph coloring has spurred.

• Quick coverage of solutions to the mid-term.
• The power of randomization in distributed computing: a review, and the role of symmetry breaking
• A quick review of Luby's coloring algorithm, and models & motivation for such distributed resource-allocation problems.
• The basic distributed version of Leighton-Maggs-Rao (Sections 1-4 of Lecture 21).
• Required Reading: (i) Luby's distributed algorithm in detail from Lectures 5 and 6 of the lecture notes, and (ii) the basic balls-and-bins analyses from Section 2, Lecture notes #16.

• Energy-saving in cooperative wireless networks and the domatic partition problem: a simple distributed algorithm and a better approach through the method of alteration; brief comments on the optimality of this approximation (Lecture notes #6, Section 2).
• A method to solve some non-standard inequalities: the general recipe, with a specific example seen in Lecture notes #17, Section 3.
• Negtaive correlation and concentration inequalities (Lecture notes #17, Sections 2 and 5).
• Required Reading: Lecture notes #17, Section 3 and Section 4 (Dubhashi-Ranjan's work on negative correlation in balls and bins).

• The Lovász Local Lemma:
  • Statement and proof for the symmetric case.
  • Statement of the symmetric case.
  • Applications: k-SAT, frugal coloring, and defective coloring.

• The iterated Lovász Local Lemma and getting the right leading constant for approximating the domatic partition problem (this paper gives a short description).
• The Moser-Tardos algorithm.

• The Lopsided Local Lemma (statement alone) and Latin transversals.
• A basic correlation inequality -- Harris' inequality -- for random variables defined on a totally-ordered set (also illustrates in a very simple way the idea of ghost sampling).
• The FKG inequality and examples.
• Janson's inequality:
  • Where we get the need for such an inequality (e.g., in random graphs and in network design), and why FKG points in the wrong direction.
  • The core conditional probability that needs estimation in the proofs of the Lovász Local Lemma (we need an upper bound on this probability) and Janson's inequality (here we need a lower bound); how these two different approaches then work.
  • Statement of the inequality and the beginning of the proof.
• Required Reading: Section 2 of Lecture Notes #26 and Lecture Notes #27, for a typical connection between FKG and the Lopsided Local Lemma, and an introduction to Janson's inequality.

• Proof of the basic Janson inequality, and its extension to the regime \Delta > \mu via the probabilistic method.
• Start the Group Steiner Tree problem.

• The Garg-Konjevod-Ravi approach to Group Steiner on trees: valid constraints, novel rounding algorithm, and analysis via Janson.
• "Capacity installation" interpretation of the LP to give intuition for how the valid constraints were arrived at.
• Is there a systematic way to generate valid constraints? The maximum independent set problem, and work since the 1980s (up to ongoing research on Sum-of-Squares hierarchies) to automatically generate valid constraints.
• The complexity of edge coloring; motivate and start distributed resource allocation.

• The Panconesi-Srinivasan algorithm for distributed edge-coloring, and a negative-correlation-based approach to one side of the bipartition.
• Why the other side of the bipartition is harder to handle.
• Martingales, and two Martingale tail bounds due to McDiarmid; note the freedom the latter offers in terms of ordering the undrlying random variables in a manner favorable to us.
• Start the Martingale-tail-bound-based approach of Dubhashi to handle the more-challenging side of the bipartition.

• Finish the approach of Dubhashi, but without the coupling.
• Dimension reduction and the Johnson-Lindenstrauss Lemma.
• Start the Dasgupta-Gupta proof of the Johnson-Lindenstrauss Lemma.

• Finish the Dasgupta-Gupta proof.
• General discussion of metric embeddings.
• Start tree embeddings.

• Full proof of the Fakcharoenphol-Rao-Talwar tree embedding from Section 8.5 of Williamson-Shmoys.
• Required Reading: Section 8.6 of Williamson-Shmoys, for a concrete use of tree embeddings. (It is also a good exercise to see how the Group Steiner Tree problem reduces to one on trees in this manner.)

• Submodularity and examples.
• The weighted maximum coverage problem.
• Dependent rounding for a list of probabilities, proofs of its basic properties, and application to maximum coverage (with improvements to special cases such as the budgeted maximization version of vertex cover).

• A quick recap of the negative cylinder dependence of the dependent-rounding scheme we saw.
• The pipage rounding work of Ageev and Sviridenko, which preceded our dependent-rounding scheme (and which can be viewed as a derandomized version of the latter in many cases).
• Recap of why the tight constraints at a vertex of a polytope span the entire ambient space.
• Matroids, the greedy algorithm for linear-function optimization over them, and matroid intersection.
• How submodular functions inherit useful properties of concavity (the law of diminishing marginal returns) and convexity (minimizability in polynomial time via the Lovasz extension -- which in turn relies on a "minimum-entropy dependent rounding" approach).
• The matroid rank function and its submodularity.
• Optional Reading: The book by Lau, Ravi and Singh provides excellent coverage of most topics in this lecture.

• Quick coverage of topics related to matroids, submodularity, and pipage/dependent rounding:
  • Recap of the greedy algorithm for optimizing a linear function over a matroid.
  • Matroids as an abstraction of linear independence.
  • The matroid- and matroid base- polytopes, and their efficient separation oracles.
  • The chain structure of the tight sets at the vertices of the matroid- and matroid base- polytopes, and their consequences for the integrality of these polytopes, as well as for the matroid intersection polytope.
  • Very quick coverage of the powerful pipage/dependent rounding approach of Calinescu, Chekuri, Pal, and Vondrak for maximizing a monotone submodular function subject to a matroid constraint.
• Solutions to selected HW/project problems, especially those with challenging covariance calculations.
• Optional Reading: The book by Lau, Ravi and Singh provides excellent coverage of many topics in this lecture.

Web Accessibility