Courses / DescriptionsEECS 495: Analytical Methods in Theoretical Computer Science
Quarter OfferedFall : 12:30-1:50 TuTh ; De
PrerequisitesBy instructor permission.
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:
- Fourier representation on finite probability spaces. Chaos decomposition in Gaussian spaces.
- Application: Fourier learning.
- Hyper-Contraction in hypercube and Gaussian spaces.
- Influences. Lower bounds on influences.
- Noise sensitivity and applications
- Gaussian and Spherical measures in high dimensions.
- Application: isoperimetric inequalities.
- Invariance principles.
In general, we will be covering a cross of topics from these two courses:
COURSE INSTRUCTOR: Prof.
BACKGROUND: Some background in probability and analysis with an interest in discrete mathematics.