The following is an approximate outline of the main topics covered in CMSC858C, Fall 2011 up to the end of October.

High-Level Picture:

• The power of randomized algorithms: abundance of witnesses and zero-sum games, applications of the probabilistic method (e.g., when there is no obvious best choice for a combinatorial structure), symmetry-breaking in networking and distributed computing, laws of large numbers & concentration (e.g., in sampling and streaming-type algorithms).
• Pseudorandom generators (ad hoc and rigorous), computing with weak random sources, "weakly-random" inputs as plausible explanations for the success of algorithms in practice; randomized algorithms can often be derandomized; the "P = BPP" conjecture.

• Concavity and convexity, Jensen's inequality, Stirling's approximation, bionomial coefficients, and binomial sums.
• Basic facts about convex optimization and linear programming; existence of fractional solutions with good properties based on the rank of the tight constraints (e.g., flow decomposition).
• A simple "master method" for solving non-standard inequalities.
• (Finite) Fields, polynomials, and Vander Monde matrices.
• The expectation: two interpretations and alternative formula; expectation vs. median; the linearity of expectation.
• The union bound.

• Tail bounds: Markov, Chebyshev, Chebyshev-Cantelli, moment inequalities, Bellare-Rompel, Schmidt-Siegel-Srinivasan.
• The Bernstein-Chernoff-Hoeffding bounds and the role of convexity; approaches to "small" and "very large" deviations; lower-bounds on tail probabilities and the Poisson approximation.
• The simplifying role of the elementary symmetric polynomials: Schmidt-Siegel-Srinivasan.
• Random sampling (using "few" random bits).
• The Hajnal-Szemeredi theorem and application to tail bounds; Janson (2004)'s tail bounds parametrized by the fractional chromatic number of the dependency graph.
• Negative correlation and negative association; FKG; Dubhashi-Ranjan; tail bounds under negative correlation.

• The methods of conditional probabilities and pessimistic estimators.
• Advice strings and their explicit construction; RP, coRP contained in P/poly.
• Randomized algorithms wherein a weak randomness property of the random source is sufficient:
  • k-wise independence: connection to linear independence, constructions, lower bounds.
  • Almost k-wise independence and Fourier analysis.
  • Other applications of small sample spaces: hashing, document filtering, min-wise independence.
• Existence proofs for small sample spaces: probabilistic, or based on linear programming.
• Computing with weak random sources and connection to highly unbalanced "random-like" bipartite graphs.
• Brief discussion of deterministic amplification by random walks on expanders; (strong) randomness extractors and privacy amplification.

• See this very interesting blog post by Terry Tao on the crossing number, and a memorable quote from there: "However, there is an amazing (and unintuitive) principle in combinatorics which states that when there is no obvious "best" choice for some combinatorial object (such as a set of vertices to delete), then often trying a random choice will give a reasonable answer, if the notion of "random" is chosen carefully. (See this paper of Gowers for some further discussion of this principle.) The application of this principle is known as the probabilistic method, first introduced by Erdos."
• Graph Ramsey Theory, random graphs, and Ramsey graphs.
• Alteration and random permutations as integral to the probabilistic method.
• Probabilistic existence proofs via large-deviation bounds.

• Connections between the basic randomized complexity classes.
• Randomized Quicksort and selection.
• Hashing and communication complexity.
• Graphs and hypergraphs: dominating sets, independent sets, and coloring.
• Balls and bins.
• Randomized geometric algorithms and backwards analysis: smallest enclosing disks.
• Algorithmic game theory and economics: incentive compatibility, mechanism design (with or without money) & VCG, social choice functions, Arrow's Theorem and the Gibbard-Satterthwaite Theorem; auctions, submodularity, coverage functions, and (approximately) truthful-in-expectation randomized mechanisms.
• Metric embeddings and distortion: Bourgain and Johnson-Lindenstrauss.
• Approximation algorithms, packing/covering, and fractional relaxations; deterministic vs. randomized rounding ("scale fractional solution up/down and keep many random variables close to their means simultaneously"): independent rounding with/without alteration.

Web Accessibility