Course material

Lecture notes

Similarity Search in High Dimensions Lecture 1 by Piotr Indyk

Similarity Search in High Dimensions Lecture 2 by Piotr Indyk

Similarity Search in High Dimensions Lecture 3 by Piotr Indyk

High-dimensional combinatorics Lecture 1 & 2 by Nati Linial

The simplex algorithm and the Hirsch conjecture Lecture 1 by Thomas Dueholm Hansen

The simplex algorithm and the Hirsch conjecture Lecture 2 by Thomas Dueholm Hansen

The simplex algorithm and the Hirsch conjecture Lecture 3 by Thomas Dueholm Hansen

Embedding and sketching Lecture 1 by Alexandr Andoni

Embedding and sketching Lecture 2 by Alexandr Andoni

Embedding and sketching Lecture 3 by Alexandr Andoni

List of background literature:

  • Especially related to Ken Clarkson's lectures on "Metrics, Nets, Measures, Dimension, and Search":

Nearest-neighbor searching and metric space dimensions, in G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006.

  • Especially related to Nati Linial's lectures on "High-dimensional combinatorics":

What are high-dimensional permutations? How many are there? from a talk given at: IPAM reunion meeting in combinatorics, Lake Arrowhead, June '11

An upper bound on the number of high-dimensional permutations, Paper by Nati Linial and Zur Luria.

  • Especially related to Thomas Dueholm Hansen's lectures on "The simplex algorithm and the Hirsch conjecture":

J. Matousek, M. Sharir and E. Welzl.
A subexponential bound for linear programming
Algorithmica, 16(4-5):498-516, 1996.

F. Santos.
A counterexample to the Hirsch conjecture
CoRR, abs/1006.2814, 2010.

F. Eisenbrand, N. Hähnle, A. Razborov and T. Rothvoß.
Diameter of Polyhedra: Limits of Abstraction
Math. Oper. Res. 35(4):786-794, 2010.

T. D. Hansen, P. B. Miltersen and U. Zwick.
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
In Proc. of 2nd ICS, 2011.

O. Friedmann, T. D. Hansen and U. Zwick.
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
In Proc. of 43rd STOC, 2011