Convexity

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Natalia Karaskova

News & Log

18.09: Introduction to convex sets. Separation theorem, Radon’s lemma and Caratheodory’s theorem. The content on this lecture can be found in Chapter 1 of Lectures on Discrete Geometry by Jiri Matousek.

 28.09: Helly’s Theorem, Minkowski’s Theorem and its applications, General Lattices: Chapters 1 and 2  of Lectures on Discrete Geometry by Jiri Matousek.

05.10: Diophantine equation (ch. 2 of J. Matousek). Dual Lattice, packing and covering raduis (ch. VII of A course in Convexity by A. Barvinok).

12.10: Theorem of Lagarias, Lanstra & Schnorr and Flatness Theorem (A. Barvinok, ch. VII, 7. – 8.), John’s Ellipsoid (J. Matousek, ch.13.4).

19.10: Volumes in high dimension: volume of a unit ball (J. Matousek, ch. 13.1) and hardness of approximating the volume of a convex body (more complex version can be found in J. Matousek, ch. 13.2).

26.10: Brunn-Minkowski inequality (J. Matousek, 12.2), Measure concentration on the sphere (J. Matousek 14.1).

02.11: Measure concentration on the sphere (J. Matousek 14.1), Metric Embeddings (Lecture notes on Metric Embeddings by J.Matousek).

09.11: Gaussian random variables, subgaussian tails, Random projection lemma with independent Gaussian coefficients (ch. 2.1 – 2.3 of lecture notes on Metric Embeddings by J. Matousek).

16.11: Johnson-Lindenstrauss Lemma. Different proofs of Random Projection Lemma using Gaussian Annulus Theorem and Levy’s Lemma. (see 14.3 and 15.2 of J. Matousek for some of the material covered).

27.11: Convex polytopes. “A H-Polytope is a V-Polytope”.

30.11: “A V-Polytope is a H-Polytope” using Fourier-Motzkin elimination. Hyperplane arrangements.

07.12: Clarkson’s theorem on level k vertices in a hyperplanes arrangment, proof in 2D. Weighted Majority Algorithm.

14.12: Randomized Weighed Majority Algorithm and it”s application in Convex Optimization.

Description

Convexity is fundamental concept in mathematics. This course is an introduction to convexity and its ramifications in high-dimensional Geometry.

Here you can find out more about the course.

Schedule

Lecture: Monday 08:15 – 10:00 (MA A1 12); 
Exercises: Friday 08:15 – 10:00 (MA A3 30); 

 

Office hours: Thursday 9:00 – 10:00 (MA C1 563)

Grading

Your grade will be determined by a written exam during an exam session. You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you solve 50% or more of the exercises, the grade of your final exam will be improved by a half grade. If you solve 90% or more of the exercises, the grade of your final exam will be improved by a full grade.

 

You can find a practice exam here.

Assignments

We will publish an assignment sheet with problems and practical exercises on the webpage every week after the lecture. You can work on the exercises, ask questions, and discuss problems during the exercise sessions. You will have the opportunity to hand in written solutions for feedback. Exercises must be submitted individually. 

Correct solutions to selected “star” problems give you bonus points. The deadline is one week after the sheet is issued. More precisely, you can either hand in the solutions to the assistant during the exercise session, or leave your solutions in the box next to MA C1 563 (be sure to put them in the correct box) or send them via email by 16:00 on Monday.

We will discuss solutions during the exercise sessions.

Literature

  1. Jiri Matousek, Lectures on Discrete Geometry.
  2. Alexander Barvinok, A Course in Convexity.
  3. Jiri Matousek, Metric Embeddings, Lecture notes (http://kam.mff.cuni.cz/~matousek/ba-a4.pdf)