Time Schedule:
James Russell Lee
CSE 599
Seattle Campus
Studies of emerging areas and specialized topics in computer science.
Class description
Structure preserving maps from one geometric space to another have become a major tool in the development of approximation algorithms for a number of classical NP-hard problems. We will study the theory of such embeddings, as well as some of the most spectacular applications in computer science.
A large component of the course will deal with high-dimensional non-linear geometry and high-dimensional probability; these have become essential tools in the analysis of semi-definite programming relaxations, and in the design of algorithms for high-dimensional search. We'll also look at some Fourier-analytic approaches, and the connections to geometric "rigidity," PCPs, and hardness of approximation.
Student learning goals
General method of instruction
Recommended preparation
Class assignments and grading
