Lecturer
Assistant
News & Log
22.09.: Convex Sets, Theorems of Caratheodory, Radon, Helly, Chap. 1.2, 1.3 in Matousek; introduction to lattices, Minkowski’s first theorem, Chap. 2.1, 2.2 in the same book
29.09.: Minkowski’s second theorem, Chap. 1.8 in the lecture notes of Thomas Rothvoß; John’s theorem, Chap. 2.1 in the lecture notes of Thomas Rothvoß
06.09.: Dual Lattices and the Flatness Theorem, Chap. 7 & 8 in Barvinok
There was no lecture and no class on October 13, 2016
20.10.: Continuing Flatness Theorem and equivalence of finitely generated and polyhedral cones
27.10.: Continuing on cones, in particular the Minkowski-Weyl Theorem, Introduction of Voronoi cells
03.11.: Affine hull, dimensions of polyhedra, faces and facets, limiting the number of facets of a Voronoi cell, cf. Schrijver
10.11.: The CVP algorithm via Voronoi Cells of Micciancio and Voulgaris
17.11.: The LLL algorithm
24.11.: The volume of the unit ball and Gaussians, volumes of polyhedra
01.12.: Brunn’s inequality and the Brunn-Minkowski inequality, cf. Matousek
08.12.: Concentration of Measure on the Sphere, Random Projections
15.12.: Random Projections, Gaussian Annulus Theorem, Johnson-Lindenstrauss Theorem
Description
Convexity is a 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: Thursday 14:15 – 16:00 (INM 203);
Exercises: Thursday 16:15 – 18:00 (INM 203);
Office hours: Wednesday 11:00 – 12:00 (MA C1 573)
Final Exam
The final written exam will take place on Monday, January 16, 2017 from 8:15 to 11:15 (please be there on time) in room CE1101.
You can view your exam on Thursday, Feburary 9, 2017 at 14:00 in room MA B1 524.
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 score an average of 50% or more in the exercises, the grade of your final exam will be improved by a half grade. If you score an average of 90% or more, the grade of your final exam will be improved by a full grade. The bonus points will be awarded only to students who get a grade of at least 4 in the exam.
Assignments
We will publish an assignment sheet with problems and practical exercises on the webpage every week before 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.
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 573 (be sure to put them in the correct box) or send them via email by 14:00 on Thursday.
Star-exercises can be handed in by groups of up to 3 people.
- Assignment 01 Solution 01
- Assignment 02 Solution 02
- Assignment 03 Solution 03
- Assignment 04 Solution 04
- Assignment 05 Solution 05
- Assignment 06 Solution 06
- Assignment 07 Solution 07
- Assignment 08 Solution 08
- Assignment 09 Solution 09
- Assignment 10 Solution 10
- Assignment 11 Solution 11
The following questions are thought to give you help by reviewing the topics of the lecture. They do not aim to cover the whole lecture, but rather give you an idea on the kind of questions you could have in mind when repeating the content of the course.
- Questions for the exam preparation
Literature
- Jiri Matousek, Lectures on Discrete Geometry.
- Thomas Rothvoß, Integer Optimization and Lattices, Lecture notes (https://www.math.washington.edu/~rothvoss/583D-spring-2016/IntOpt-and-Lattices.pdf)
- Alexander Barvinok, A Course in Convexity.
- Jiri Matousek, Metric Embeddings, Lecture notes (http://kam.mff.cuni.cz/~matousek/ba-a4.pdf)