Week 1: Probabilistic Inequalities

Scribe: Weijun Xie

  • Probability distributions: Bernoulli, Gaussian, Poisson, Logconcave
  • Convergence to Gaussian: Berry-Esseen
  • Concentration Inequalities: Markov, Chebychev, Chernoff-Hoeffding, Bernstein, Azuma, McDiarmid, Janson, Lovasz, Talagrand, Kannan
  • Sample applications: Randomized rounding, JL lemma

The Probabilistic Method (Alon-Spencer), Randomized Algorithms (Raghavan-Motwani, Mitzenmacher-Upfal), The Random Projection Method (Vempala).