The main prerequisite is mathematical maturity. However, we will assume the students are comfortable with / can quickly pick up the basic concepts in:
- Linear algebra: vector & dual vector spaces, determinants, gram schmidt orthogonalization, etc.
- Basic Convexity: duality, separation results, polar of convex sets, norms, dual norms, etc.
- Probability & Probabilistic algorithms: Gaussians, Chernoff bounds, Monte Carlo algorithms. For some useful lectures notes, see: https://www.cs.cmu.edu/~odonnell/papers/probability-and-computing-lecture-notes.pdf
Aim of the course:
The geometry of convex bodies in high dimensions and correspondingly of normed vectors spaces is a beautiful subject of study that has fascinated mathematicians for over a hundred years. Questions that have driven the field include: how does measure concentrate in high dimensions? how close is every convex body to an ellipsoid? how much can one improve upon on the triangle inequality? To what extent does the parallelogram law hold? To gain a deep understanding of these questions, still today the subject of very active research, powerful techniques were developed by leveraging surprising connections between geometry, analysis and probability. These have now found numerous applications across mathematics and computer science. In particular, a rich interplay of continuous and discrete mathematics has developed in recent years.
The aim of this course is to both cover the fundamentals of the area as well as selected applications.
Possible fundamental topics include:
- the geometry of normed spaces
- sums of Banach space valued random variables
- the concepts of type and cotype
- embeddings into l_2 and l_1
- Grothendieck's inequality
- functional inequalities such as Prekopa-Leindler and Brescamp-Lieb
- isoperimetric inequalities and logconcave measures.
Possible application areas include:
- algorithms for volume estimation
- combinatorial discrepancy
- spectral graph theory
- error correcting codes
Daniel Dadush (CWI)
Jop Briet (CWI)