Class Venue and Time: CSI 2120, 12:30-1:45AM Tue, Thu

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

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. 27, 2015:**

- 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**

- The expectation and its two interpretations that will be of use to us; expectation vs. median; the linearity of expectation.
- An elegant application of the linearity of expectation to
Buffon's
*noodle*: be careful with the linear-function hypothesis! **Additional Reading:**See Timothy Gowers' blog post, esp. Example 1, on Zorn's Lemma and the linear-function hypothesis

- 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 its analysis.
- Markov's inequality, and refined (repeated early-stopping) application of it to algorithms (such as Randomized Quicksort).
- Chebyshev's inequality, and examples that compare it to Markov.
- Risk and variance.

- A careful look at conditioning.
- The union bound and Markov's inequality; properties of truncated inclusion-exclusion; collisions in random functions.
- Variance, Jensen's inequality, variance of a sum, co-variance and correlation, negative correlation in sampling without replacement, the "square-root phenomenon" in tail bounds.

- Fourth-moment discussion to understand the distance traveled by the standard random walk on the integers
- The normal and Poisson limits, and a brief introduction to Poisson approximation (with the example of the number of fixed points of a random permutation).
- Las Vegas and Monte Carlo algorithms, randomized complexity classes,
and exact
characterization of
*ZPP*. - More on the probabilistic method: Ramsey graphs, and Szele's lower bound on the maximum possible number of Hamiltonian paths in n-vertex tournaments.

- Alon's
**upper**bound on the maximum possible number of Hamiltonian paths in n-vertex tournaments. - Viewing
**alteration**and**random permutations**as integral to the probabilistic method; dominating sets in graphs with lower-bounded min-degree -- vanilla method and the power of alteration. - Detailed discussion of related alteration approaches for dominating set, with a focus on trying to improve the lower-order term.

- Four probabilistic approaches for constructing "large" independent sets, and their analyses: vanilla method, alteration, alteration along with the natural idea of random permutations, random permutations alone.
- Paradigms for distributed algorithms: contention resolution,
**symmetry-breaking**and local alteration, illustrated by Luby's algorithm for (Δ + 1)-coloring (with some variants reserved for the homework).

- Complete the analysis of Luby's distributed algorithm; discussion of the "symmetry-breaking" paradigm.
- Perspectives on the power of random permutations:
- via the
*implicit*abundance of good witnesses (orderings of the data, in this case); - as a worst-case-to-average-case reduction: randomized algorithms vs. probabilistic analysis, a basic introduction to Blum-Kannan program-checking using random self-reducibility (which is one way of achieving worst-case-to-average-case reductions), and brief mention of the random self-reducibility of the permanent.

- via the
- Two-coloring uniform hypergraphs: lower and upper bounds due to Erdös, and the probabilistic method as applied to "[there exists] [for all]" and "[for all] [there exists]" statements.

- Attacks on hash functions such as MD5, and some useful tools for asymptotic calculations: what happens in the birthday paradox when the number k of elements (chosen from n elements) is: O(n^{1/2})? O(n^{2/3})? ... Theta(n)?
- Two-coloring uniform hypergraphs:
- Why "#vertices = edge-size-squared" is the right choice for #vertices: the design and analysis of a different randomized algorithm when #vertices is noticeably smaller.
- The Radhakrishnan-Srinivasan approach.

- Conjectures and progress on two-coloring: the uniform and non-uniform cases.
- Selection using the first-moment and second-moment methods; the
power of
**random sampling**:- a standard recipe with random sampling: imagine an ideally-spread sample and design a skeleton algorithm; add some slack to it to allow for random variables deviating from their mean; and use suitable tail bounds to show that these deviations are contained within your slack with high probability;
- why is the first-moment insufficient in our second-moment-based analysis?

- Complete selection using the second-moment method.
- The Bernstein-Chernoff-Hoeffding bounds: different regimes of interest, examples; application to random sampling.
- A brief high-level discussion of the power of large-deviation theory.

- Amplification of the success probability for BPP, BPP contained in P/poly, approaches in the 1980s to P vs. NP, and modern barriers.
- A brief digression on alternatives to worst-case complexity -- especially smoothed complexity as introudced by Spielman and Teng.
- The
**balls-and-bins**paradigm and max. load in balls-and-bins -- small deviations, and why the "log n" and "1/ε^2" terms often come up naturally (to be seen again later in the Johnson-Lindenstrauss Lemma).

- Balls-and-bins: the lightly-loaded case, and a simple approach to
*very large*deviations. - A "master method" to solve non-standard inequalities.
- The power of randomization in distributed computing: basic resource-allocation modeled as bipartite edge-coloring, graph-theoretic background on edge-coloring, start Panconesi-Srinivasan approach to distributed resource-allocation.

- The Chernoff bounds under negative correlation, and application to balls-and-bins and distributed resource-allocation.
- Recap of class thus far, with an emphasis on the big picture and major paradigms/tools to keep in mind.
- The power of dimension-reduction, and statement of the Johnson-Lindenstrauss Lemma.

- Tightness of the Chernoff bounds; discussion of power-law behavior, "long tail" phenomena, and models for networks that arise in practice
- Negative correlation and tail bounds for (non-binary) bounded random variables.
- Negative association in balls-and-bins: the main result of Dubhashi-Ranjan, and application to
*lower*bounds on max. load in balls-bins. - Basic ideas behind the Dasgupta-Gupta proof of the Johnson-Lindenstrauss Lemma.
**Assigned reading:**Read the full Dasgupta-Gupta proof.

- More discussion of
**metric embeddings**: Bourgain and Bartal. - Large cuts, a simple construction of pairwise independent random bits, and proof of pairwise independence.

- Large cuts, pairwise independence, and small sets of derandomizing
"advice strings" for all
*n*-vertex graphs. - Fields: basic properties, Vandermonde matrices, and low-degree polynomials.
- Reed-Solomon codes and
*k*-wise independence. - Data streams: the Alon-Matias-Szegedy F_2 estimator, and the power of
**linear sketches**. - A brief discussion of compressed sensing.

- The
**Lovász Local Lemma**:- the symmetric version, and applications including defective vertex coloring, independent transversals, and hypergraph coloring;
- proof of the symmetric version;
- a definition of dependency graphs, the lopsided LLL, and application to improved hypergraph coloring.

- More on the LLL:
- compactness for when the number of bad events is infinite;
- the asymmetric LLL, and frugal vertex coloring as an example;
- the iterated LLL and an application to domatic partition;
- the Moser-Tardos algorithm without proof.

**Required reading:**Proof of correctness of the Moser-Tardos algorithm.

- Recap of the LLL.
- Linear programming (LP): examples and geometry.
- A brief history of major advances in LP: Simplex, exterior-point methods, interior-point methods, smoothed analysis, and fast modern (1 + epsilon)-approximations.
- The issue of strong polynomiality and the work of Éva Tardos.
- The polyhedral approach to combinatorial optimization
- (Weighted) vertex cover: 2-approximation via LP, remarks on the polytope, the best-known (2 - o(1))-approximation, inapproximability and the Unique Games Conjecture, parametrized complexity.
- Approximation algorithms for set cover: the randomized-rounding philosophy, alteration vs. "Chernoff + union bound"

- Dependent rounding for s-t min-cut.
- Dependent rounding for distributions on level-sets: budgeted set cover, negative correlation, and the rounding method with proof.

- Pipage rounding (randomized): generalization of previous class' construction to bipartite graphs, and the integrality of the bipartite-matching polytope.
- A quick tour of some topics in combinatorial optimization:
- Extended formulations and the case of non-bipartite matching.
- Remarks on convex programming, the ellipsoid method, and the sufficiency of a separation oracle.
- Positive semidefiniteness, semidefinite programming, and the Goemans-Williamson algorithm with proof.

- The FKG inequality and an application to large independent sets in hypergraphs.
- A brief introduction to parallel computation, the classes NC and RNC, and some basic parallel algorithms.

- A detailed understanding and proof of the Moser-Tardos algorithm.

- Multi-way cut and modern dependent rounding due to Buchbinder-Naor-Schwartz.

- Recap of the course.