CS 860: Advanced Topics in Algorithms and Complexity Theory, Winter 2016

Winter 2016

- Term
- Winter 2016
- Lectures
- Wednesdays, 10:00am-12:20pm

DC 3313 - Instructor
- Eric Blais
- Piazza page
- Here.

The

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.

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.

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.

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.

- 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.
- Isoperimetry
- Isoperimetric inequalities on the hypercube and Gaussian spaces.
- Influence of variables
- Inequalities on the influence of variables. Threshold phenomena.