Concentration Inequalities in Computer Science
CS 860: Advanced Topics in Algorithms and Complexity Theory, Winter 2016

CS 860: Concentration Inequalities in Computer Science
Winter 2016

Winter 2016
Wednesdays, 10:00am-12:20pm
DC 3313
Eric Blais
Piazza page

What is this course about?

The concentration of measure phenomenon. In short: with a single random variable (say, the flip of one fair coin), then there usually isn't anything about this variable that we can predict with any reasonable confidence. With a large number of independent random variables, however, there are lots of predictions we can make with high confidence (for example, with 10000 coin flips, roughly 1/2 of them will land heads; the longest run of heads or tails will be of length roughly 100; etc.) Concentration inequalities give bounds on the probability that these predictions are wrong.

What does this have to do with computer science?

Lots! As it turns out, concentration inequalities have many deep and surprising implications in the analysis of randomized algorithms and in complexity theory. They are a key ingredient in numerous results in sublinear-time algorithms, compressed sensing, communication complexity, the analysis of Boolean functions, dimension reduction and machine learning, etc.

So what will this course cover?

We will explore some of the main concentration inequalities and their applications to various problems in theoretical computer science. Our emphasis will be to understand how to use these inequalities in our problems rather than how they are proven, and we will do this by exploring the use of concentration inequalities in a wide variety of different topics within computer science.

The only prerequisite for the course is mathematical maturity. Specifically, we will be establishing formal proofs for the analysis of algorithms andncomplexity theoretic results, so familiarity (and interest in!) these kinds of proofs, as well as a background in probability theory and the analysis of algorithms, will also be required. No prior exposure to concentration inequalities is required, and all of the computer science topics in which we will apply those inequalities will be introduced in the course itself.

How will the course be structured?

Most of the lecture time will be devoted to problem solving sessions. The concentration inequalities will be introduced briefly in class, and then reading assignments (consisting of recent computer science papers) will be given for the week to deepen the understanding of how we use the inequalities. Then, on the following week, we will solve other related problems as a group in class.

The other main component of the course will be a class project. Each student will be expected to apply some of the tools covered in the course to research problems in their areas of interest.

Where can I find more information?

1. See the textbook Concentration inequalities: A nonasymptotic theory of independence by Stephane Boucheron, Gabor Lugosi, and Pascal Massart for a preview of the content of the course.
2. Scroll down for a more detailed list of topics.
3. Contact the instructor, Eric Blais, with any other question.

Tentative list of topics

Basic inequalities
Chernoff-Hoeffding, Bernstein, and Azuma inequalities.
Variance and concentration
Efron-Stein inequality. Bounded differences inequalities.
Entropy method
Information theory inequalities. Logarithmic Sobolev inequalities. Hypercontractivity.
Isoperimetric inequalities on the hypercube and Gaussian spaces.
Influence of variables
Inequalities on the influence of variables. Threshold phenomena.

Cover photo: Magnetic Teslas by Martin Latter (2006).
Site designed with Bootstrap.