Advance Theoretical Computer Science - Selected topics in combinatorial, convex, and high dimensional geometry

2015 Spring

Lecturer: Jian Li

We intend to cover a subset of the following topics (tentative):


(1) (first half) Combinatorial and Computational Geometry: Some classical combinatorial geometry like Helly theorem, Ham-Sandwich theorem and some equi-parition problems related to topology. Arrangement, geometric duality, VC-dimension, epsilon-net, geometric discrepancy, geometric coreset, cutting, (maybe : Triangulations, fixed dimensional LP and LP-type problems, some geometry data structures).

Polyhedra geometry: basic Polyhedra combinatorics, Face lattices, Polarity, Morse functions, Dehn-Sommerville equations, upper bound theorem, Kalai's theorem on simple polytope.

 
(2) (second half) Convex Geometry and High Dimensional Geometry (By saying high dim geometry here, it does NOT mean that the first part is about low dimensional geometry. It means that the dimension is not a fixed number, but grows as a parameter. On the contrary, the first part mostly concerns with fixed dimensional space):

We will cover an important phenomena raised in high-dimensional geometry, the concentration of measure (you probably heard the name from probability theory, like Chernoff bounds, but it is really a geometric notation. And this is where geometry really meets probability theory). Isoperimetric inequalities. Talagrand's distance (maybe: Poincare inequality, log-sobolev inequality, Brun-Minkovski inequality and applications.)

Maybe: Metric embedding: Johnson-Lindenstrauss lemma, Bourgain's theorem, and applications to approximation algorithms.

Depending on the progress, we will probably cover some convex optimization algorithms and empirical process (how geometry interacts with probability), which are also important topics in machine learning.

Some of the convex geometry stuffs are related to John's convex optimization class http://itcs.tsinghua.edu.cn/~john/convex2013.html and a previous course by myself. But it will be fine if you didn't take those courses.

Grading:

  1. Homeworks (30pts, 1 homework every two weeks)
  2. 5pts for taking notes: Each student should take notes for at least one lecture (maybe two), using LaTex (use this template sample.tex algorithm2e.sty).
  3. 1 take-home final, till the end of the semester (30pts)
  4. 1 course project (35pts)  I will suggest some project topics around the 3rd or 4th week.

Schedule:

Every Mon 9:50-12:15

Room: 6A 113

Mar 2 Overview. Caratheodory theorem, Radon's lemma, Helly theorem, Ham-Sandwich theorem, Borsuk-Ulam Theorem (some equivalent forms, and an informal proof without using topology). notes
Mar 9 An equi-partition problem via Ham-Sandwich cut. Sperner's lemma, Tucker's Theorem, Brouwer's fixed point. Kneser's conjecture (Kneser-Lovasz theorem), Inscribed Chord; Starting Arrangement note
Mar 16 Arrangement, Count the number of faces in the arrangement of n hyperplanes, zone theorem, Arrangement of segment and Davenport-Schinzel sequence. Geometric Duality, Face Lattice, Polarity 　
Mar 23 Face Lattice, Polarity, Simplicial/simple polytopes, Cyclic polytope and upper bound thm (no proof), Morse function, A fractional helly thm, Counting faces (Dehn-Somnerville equations) 　
Mar 30 Blind&Mani Theorem (with Kalai's proof). Linear programming, Simplex Algorithm (the geometric view, no tableau), Ellipsoid algorithm and interior point algorithm (no detail). Randomized incremental algorithm for convex hull in 2D. Randomized incremental algorithm for LP in fixed dimension (Seidel's algorithm). 　
Apr 6 VC-dimension, many examples, Sauer's lemma, eps-net, eps-approximation, a probabilistic construction of eps-net, 　
Apr 13 (1/eps)-sized eps-net for halfspaces in R3. Geometric set cover via multiplicative re-weighting. Geometric set cover via LP and eps-net. Clarkson's randomized algorithm for LP (two algorithms). 　
Apr 20 Discrepancy. From discrepancy to eps-approximations, Chazelle-Matousek's deterministic construction. Low-stabbing spanning tree, better bounds for eps-approximation via discrepancy (better than sampling).　 　
Apr 27 product range space, eps-cutting, point location query incidence, Hopcroft problem 　
May 4 Labor day (no class) 　
May 11 optimal partition tree (no details), simplex range query. Start high dimension. The volume of the ball in R^n, the phenomena of measure concentration (for unit ball in Rn) 　
May 18 Banach-Mazur distance (analytic and geometric definition). John's ellipsoid (proof  convex programming and KKT condition). Euclidean section of a hypercube (a hypercube C^n has a almost Euclidean section of dimension O(log n), the spherical cap volume packing argument). 　
May 25 Brunn-Minkowski inequality, isoperimetric inequality in R^n, Prékopa–Leindler inequality (no proof), isoperimetric inequalities for sphere and Gaussian. Measure concentration for Lipchitz functions. 　
Jun 1 Talagrant inequality with applications. Empirical process (only an overview). 　
　 　 　

The scribe notes are not polished yet and we do not guarantee correctness. Use them at your own risk.

　

References:

[Book] Lectures on Discrete Geometry, Matousek

[Book] Lectures on Polytopes, Ziegler

[Book] Combinatorial Geometry, Pach, Agarwal

[Book] The Discrepancy Method: randomness and complexity, Chazelle

[Book] Computational Geometry: Algorithm and Applications, de Berg, van Kreveld, Overmars, Schwarzkopf

[Book] Geometry Approximation Algorithms, Har-Peled

[Book] Concentration of Measure for the Analysis of Randomized Algorithms by D. P. Dubhashi and A. Panconesi, Cambridge University Press, 2009.

[Lecture notes] Lectures on Discrete and Polyhedra Geometry, Igor Pak [link]

[Lecture notes] Probability in High Dimension, Ramon van Handel,[link]

[Survey] An Elementary Introduction to Modern Convex Geometry, Ball