Course material

Note that school material (except background literature) will be given to all participants as printed versions at the school.

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 1 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.