Courses
  /  
Descriptions
EECS 495: Analytical Methods in Theoretical Computer Science

Quarter Offered

Fall : 12:30-1:50 TuTh ; De

Prerequisites

By instructor permission.

Description

In the last two decades, theoretical computer science and discrete mathematics has benefited a lot from techniques and ideas originating in analysis.

These methods underlie many of the most spectacular advances in theoretical computer science and combinatorics including the development of probabilistically checkable proofs, computational learning theory, social choice theory and most recently additive combinatorics. This course will cover some of these methods. A tentative plan of topics is below:

  1. Fourier representation on finite probability spaces. Chaos decomposition in Gaussian spaces.
  2. Application: Fourier learning.
  3. Hyper-Contraction in hypercube and Gaussian spaces.
  4. Influences. Lower bounds on influences.
  5. Noise sensitivity and applications
  6. Gaussian and Spherical measures in high dimensions.
  7. Application: isoperimetric inequalities.
  8. Invariance principles.

In general, we will be covering a cross of topics from these two courses:

http://www.cs.cmu.edu/~odonnell/boolean-analysis/ and http://www.stat.berkeley.edu/~mossel/teach/206af05/index.htm

COURSE INSTRUCTOR: Prof. Anindya De

BACKGROUND: A strong background in probability, analysis and interest in discrete mathematics.