Lecture Schedule for CMSC858C, Randomized Algorithms, Fall 2011
Class Venue and Time: CSI 3118, 12:30-1:45AM Tue, Thu
The following is an outline of the main topics discussed in each class
of CMSC858C, Fall 2011.
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
Lecture 1, Sept 1, 2011 -- Guest Lecture by Prof. Bill Gasarch:
Lecture 2, Sept 6, 2011:
- Communication complexity: the deterministic and randomized complexities of
the Equality function (also see Bill's slides).
- Randomized protocol for polynomial identity-testing (PIT).
- Two difficulties in potentially showing that PIT is not in P:
circuit-lower-bound barriers, and our belief that P = BPP.
- Brief discussion of pseudorandom generators in conceivably showing that
P = BPP.
Lecture 3, Sept 8, 2011:
- Paradigm underlying the applications from Lecture 1: the abundance of
- Brief discussion of randomized algorithms and zero-sum games.
- The expectation and its two interpretations that will be of use to us;
expectation vs. median; the linearity of expectation.
- Alternative formula for the expectation, application to coin-flipping.
- The variance and Jensen's inequality.
- Randomized Quicksort and its analysis.
- Markov's inequality, and refined (repeated early-stopping)
application of it to algorithms (such as Randomized Quicksort).
- Randomized complexity classes.
Lecture 4, Sept 13, 2011:
- More on randomized complexity classes: amplification, and exact
characterization of ZPP.
- The union bound.
- Introduction to the probabilistic method: 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
- Viewing alteration and random permutations
as integral to the probabilistic method; dominating sets in graphs
min-degree -- vanilla method and the power of alteration.
Lecture 5, Sept 15, 2011:
- Properties of convexity, binomial coefficients, and binomial sums.
- Graph Ramsey Theory:
- Proof of the basic upper-bound, and the two regimes of interest.
- Triangle-free graphs and brief discussion of
Ajtai-Komlos-Szemeredi, Kim, and
- Random graphs and Ramsey graphs; tightness of the union bound for
(with lower-order improvements possible from the Lovász Local Lemma).
- 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
Lecture 6, Sept 20, 2011:
- Two-coloring uniform hypergraphs:
- Lower and upper bounds due to Erdös, and the probabilistic method
as applied to "exists for all" and "for all exists" statements.
- Why "#vertices = edge-size-squared" is the right choice for
#vertices (and the design and analysis of a different randomized algorithm
when #vertices is noticeably smaller).
- The Radhakrishnan-Srinivasan approach.
Lecture 7, Sept 22, 2011:
- The methods of conditional probabilities and pessimistic estimators:
large cuts, MAX SAT, and large independent sets as representative
- Large cuts, pairwise independence, and small sets of derandomizing
"advice strings" for all n-vertex graphs.
- RP, coRP contained in P/poly, and the problem of explicitly
constructing witness sets.
Lecture 8, Sept 27, 2011:
- Moment bounds: Chebyshev, Chebyshev-Cantelli, Bellare-Rompel,
- Finite fields and bounds for k-wise independence.
- Sampling with and without replacement, negative correlation, amplifying
BPP success-probabilities with limited randomness.
- Short discussion of the quality of randomness and randomness-extractors.
- Randomized selection in brief; general philosophy of designing parameters
such that several random variables stay close enough to their means, and then
proving the requisite tail bounds.
Lecture 9, Sept 29, 2011:
- Brief discussion of deterministic amplification by random walks on
expanders; strong extractors and privacy amplification.
- Fields: basic properties, Vandermonde matrices, and low-degree
- Reed-Solomon codes, k-wise independence, and Shamir's secret sharing.
- Linear independence and k-wise independence, matrix for k = 2, 3.
- Start lower bound for the size of k-wise independent
Lecture 10, Oct 4, 2011 -- Guest Lecture by Prof. David Mount:
- Alon-Babai-Itai: linear-algebraic lower bound on the size of k-wise independent
sample spaces, and almost-matching upper-bound using BCH codes.
- Almost k-wise independence: definition due to
Naor-Naor, and known upper bounds.
- Other applications of small sample spaces: hashing, document filtering,
- Elementary facts about linear and convex optimization.
- Koller & Megiddo's work on basic feasible solutions and the existence
of small sample spaces; k-wise independent
(Update: See Kuperberg-Lovett-Peled for some exciting recent progress.)
Lecture 11, Oct 6, 2011 -- Guest Lecture by Saeed Alaei:
- Welzl's randomized algorithm for computing the smallest
enclosing disk for a set of points:
Smallest enclosing disks (balls and ellipsoids), ``New Results and New
Trends in Computer Science'', (H. Maurer, Ed.), Lecture Notes in Computer
Science 555 (1991) 359-370.
- A simple randomized incremental algorithm for finding the
smallest enclosing disk for a set of n points in the plane,
and a simple "backwards analysis" of its O(n) expected running time.
- A good version is available here.
A slightly simplified presentation was used, closer to the one
given in the Computational Geometry book by de Berg, Cheong, van
Kreveld and Overmars.
Lecture 12, Oct 11, 2011:
- A very brief introduction to mechanism design: social choice
functions, Arrow's Theorem and the Gibbard-Satterthwaite Theorem,
incentive compatibility, mechanisms with/without money, and
VCG mechanisms. Reference: The Algorithmic Game Theory book edited by
Nisan, Roughgarden, Tardos and Vazirani (the book can be read online
with username = agt1user, password = camb2agt).
- Combinatorial auctions, submodularity, and coverage functions; an
(1-1/e)-approximate truthful-in-expectation randomized mechanism
Lecture 13, Oct 13, 2011:
- Perspectives on hashing and fingerprinting; the original
Carter-Wegman motivation for keeping the L_2 norm of the "number of
preimages" vector small, and pairwise independence.
- Bloom filters and heuristic analysis
- A possible explanation of the success of hashing schemes in practice:
brief description of
- The Bernstein-Chernoff-Hoeffding bounds: different regimes of interest,
comparison with Bellare-Rompel, examples; alternative approach for very
large deviations, and a "master method" for solving non-standard
Lecture 14, Oct 18, 2011:
- Metric embeddings and distortion: statements of the classical
results of Bourgain and Johnson-Lindenstrauss.
- Small deviations, and why the "log n" and "1/ε^2" terms often
come up: balls-and-bins, Dasgupta-Gupta
proof of the
- Lower-bounds on tail probabilities, and brief coverage of the
- Alternative approach to tail bounds using the elementary
symmetric polynomials: up to the end of Section 2.2 in
Lecture 15, Oct 20, 2011:
- Probabilistic existence proofs via large-deviation bounds:
- Small sample spaces for almost k-wise independence;
- Simulating BPP using a general weak random source (with background
on computing using weak random sources: von Neumann's trick, modern
formulations, Zuckerman's general weak random sources, and
modeling the problem using highly-unbalanced (random) bipartite graphs).
- Tail bounds for partially-dependent random variables: the Hajnal-Szemeredi
theorem on equitable coloring and the Rucinski/Pemmaraju approach.
Lecture 16, Oct 25, 2011:
- Fractional relaxations of combinatorial optimization problems.
- Set cover and vertex cover.
- The "uninteresting" relaxation of graph coloring, and the formulation
of the fractional chromatic number as a set cover problem; examples
and properties of the fractional chromatic number.
- The main ideas behind Janson (2004)'s tail bounds parametrized by
the fractional chromatic number.
- A detour into perfect graphs and the weak/strong perfect graph
conjectures (now theorems).
- Rounding for vertex cover.
- The basic idea behind randomized rounding; start randomized rounding with
alteration for set cover.
Lecture 17, Oct 27, 2011:
- A brief discussion of representation theory and Fourier analysis; the
work of Naor-Naor; constructing Ramsey graphs using
k-wise independence and almost k-wise independence.
- Extension of the discussion of Lecture 9: the existence of fractional
solutions with good properties based on the rank of the tight
- Set cover: approximability, and randomized rounding with alteration;
approximability of the chromatic number and independence number, and
consequences for the fractional chromatic number.
approach to congestion-minimization; flow decomposition.
Lecture 18, Nov 1, 2011:
Lecture 19, Nov 8, 2011:
- Analysis of Raghavan-Thompson and connection to balls-and-bins;
optimal (in)approximability for directed graphs, conjecture for
- The FKG inequality.
- Chernoff bounds under negative correlation.
- The powerful notion of negative association, and
negative association for the load vector in balls-and-bins.
- Set-packing and the width of packing/covering problems; analyses for
set packing using alteration and via "large deviations and
the union bound".
Lecture 20, Nov 10, 2011:
- Finish mid-term recap.
- Crossing-number description from Terry Tao's blog post.
- Methodology of tracking several random variables
simultaneously: brief description of Bohman.
- Dependent rounding: Teo-Sethuraman for s-t mincut; brief discussion of
exact LP formulations and Vazirani's study of rational convex programs.
- Dependent rounding on level-sets: Srinivasan.
Lecture 21, Nov 15, 2011:
- Finish dependent rounding on level-sets; applications to
low-congestion multi-path routing and budgeted maximum
coverage (the latter will be viewed in a more general context when
we study the work of
- Some history: the seminal work of Ageev-Sviridenko came first, and
Srinivasan's work was developed independently without knowledge of
Ageev-Sviridenko; GKPS then connected these two.
- The Lovász Local Lemma:
- motivation and versions of the lemma;
- the standard model with independent random variables driving the "bad"
events, the mutual-independence principle, and the notion of an efficient
algorithmic version of the Local Lemma;
- history, and connections to the Ramsey numbers;
- the Lopsided Local Lemma and the desirability of positive correlation
among the bad events;
- application to satisfiability.
Lecture 22, Nov. 17, 2011 -- Guest Lecture by Dr. Tom Dubois:
- Recipes for choosing the parameters x_i in the asymmetric
Local Lemma: Alon-Grytczuk-Haluszczak-Riordan on non-repetitive coloring
(the Thue number) as an example; coNP-completeness of verifying
that a coloring is non-repetitive.
- The powerful idea of iterated application of the Local Lemma:
- the domatic number and direct approach using the Local Lemma;
- the work of Feige-Halldorsson-Kortsarz-Srinivasan on getting the correct constant;
- brief description of the seminal work on
packet-scheduling due to Leighton, Maggs, and Rao.
(See my old notes
from 2001; the constant has been improved signicantly -- see
Peis and Wiese.)
- Brief discussion of the algorithmic aspect:
handling issues such as the coNP-completeness for non-repetitive coloring
Lecture 23, Nov 22, 2011:
- Algorithmic aspects of the Local Lemma:
Lecture 24, Nov 29, 2011 -- Guest Lecture by Prof. MohammadTaghi Hajiaghayi:
- Metric embeddings into tree metrics: simple examples and
history, followed by the
presentation from Section 8.5 of
- Janson's lower-tail inequalities from the late 1980s: intuition
for the case of small means (second-moment analysis that sheds light
on the relevance of Δ), followed by
the general bound (see
- Brief discussion of lower vs. upper tail bounds.
Lecture 25, Dec 1, 2011:
- Two models of computation and the role played by randomness in them:
- Parallel algorithms, the complexity class NC, the
application to finding matchings.
- The streaming model, and sample applications that require streaming
Lecture 26, Dec 6, 2011:
- Janson's bound from the late 1980s, connection to the proof idea behind the Local
- Limitations on upper-tail bounds: triangle-counts in random graphs.
- The Garg-Konjevod-Ravi approach to the Group Steiner Tree problem:
addition of valid constraints, rounding scheme, and brief sketch of the
analysis using Janson's inequality.
- The setup of Calinescu-Chekuri-Pal-Vondrak; discussion of matroids and
submodular functions (see also Lecture 11).
- The polyhedral approach to optimizing over a discrete set: compact
formulations and Yannakakis' result (see Fiorini-Massar-Pokutta-Tiwary-Wolf for recent work).
- The polyhedral structure of matroids: the matroid polytope and the
matroid base polytope, characterization of the edges of the latter.
Lecture 27, Dec 8, 2011:
- Coverage of some key ideas of Calinescu-Chekuri-Pal-Vondrak; the power
of appropriate abstractions (both matroids and submodularity).
- Brief coverage of online algorithms:
- The basic setup and competitive ratios;
- Caching and ski-rental;
- The Karp-Vazirani-Vazirani approach to online bipartite matching
(see Birnbaum-Mathieu for a simplified exposition), and lower-bounds for the
randomized online setting;
- Sponsored search and
Lecture 28, Dec 13, 2011:
- The multiplicative-weights-update method: basic ideas and
applications, following Arora-Hazan-Kale.
- Brief discussion of the connection to the Kullback-Leibler divergence
as described in Arora-Hazan-Kale, and a
nice proof of Chernoff-type
bounds using the Kullback-Leibler divergence, due to Dasgupta.
- PAC learning, VC-dimension, and coverage of
Boosting from Arora-Hazan-Kale.
- Very brief coverage of the "power of d choices".
- Quick recap of course.