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 errors.

Lecture 1, Sept 1, 2011 -- Guest Lecture by Prof. Bill Gasarch:

• 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.

• Paradigm underlying the applications from Lecture 1: the abundance of witnesses.
• 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.

• 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 probabilistic analysis.
• 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.

• 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 Bohman.
  • Random graphs and Ramsey graphs; tightness of the union bound for Ramsey graphs (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 alone.

• 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.

• The methods of conditional probabilities and pessimistic estimators: large cuts, MAX SAT, and large independent sets as representative examples.
• 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.

• Moment bounds: Chebyshev, Chebyshev-Cantelli, Bellare-Rompel, Schmidt-Siegel-Srinivasan.
• 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.

• Brief discussion of deterministic amplification by random walks on expanders; strong extractors and privacy amplification.
• Fields: basic properties, Vandermonde matrices, and low-degree polynomials.
• 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 sample spaces.

• 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, min-wise independence.
• 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 permutation families. (Update: See Kuperberg-Lovett-Peled for some exciting recent progress.)

• Welzl's randomized algorithm for computing the smallest enclosing disk for a set of points:
• Reference: 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.

• 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 due to Dughmi-Roughgarden-Yan.

• 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 (Wikipedia entry).
• A possible explanation of the success of hashing schemes in practice: brief description of Mitzenmacher-Vadhan.
• 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 inequalities.

• 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 Johnson-Lindenstrauss Lemma.
• Lower-bounds on tail probabilities, and brief coverage of the Poisson approximation.
• Alternative approach to tail bounds using the elementary symmetric polynomials: up to the end of Section 2.2 in Schmidt-Siegel-Srinivasan.

• 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.

• 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.

• 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 constraints.
• Set cover: approximability, and randomized rounding with alteration; approximability of the chromatic number and independence number, and consequences for the fractional chromatic number.
• Raghavan-Thompson approach to congestion-minimization; flow decomposition.

• Analysis of Raghavan-Thompson and connection to balls-and-bins; optimal (in)approximability for directed graphs, conjecture for undirected graphs.
• The FKG inequality.
• Chernoff bounds under negative correlation.
• The powerful notion of negative association, and Dubhashi-Ranjan 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".

• Start mid-term recapitulation of topics.
• Truncated inclusion-exclusion.
• Some of the intuition behind Stirling's formula; see Terry Tao's blog post for a full derivation.
• Graphs with large girth and large chromatic number: see Erdos' approach as well as a counting-based method.

• 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.

• 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 Calinescu-Chekuri-Pal-Vondrak).
• 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.

• 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: Moser-Tardos and handling issues such as the coNP-completeness for non-repetitive coloring (Haeupler-Saha-Srinivasan).

• Algorithmic aspects of the Local Lemma:
• Moser's initial work and the underlying information-theoretic insights;
• The work of Moser and Tardos which also cleanly addresses the asymmetric version of the Local Lemma.

• Metric embeddings into tree metrics: simple examples and history, followed by the presentation from Section 8.5 of Williamson-Shmoys.
• 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 Spencer's slides).
• Brief discussion of lower vs. upper tail bounds.

• Two models of computation and the role played by randomness in them:
• Parallel algorithms, the complexity class NC, the Isolating Lemma and its application to finding matchings.
• The streaming model, and sample applications that require streaming algorithms.

• Janson's bound from the late 1980s, connection to the proof idea behind the Local Lemma, proof.
• 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.

• 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 Mehta-Saberi-Vazirani-Vazirani.

• 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.

Web Accessibility