Low discrepancy colorings and semidefinite programming
Nikhil Bansal, TU Eindhoven
Recently, there has been interesting progress in discrepancy theory based on connections to semide nite programming. This connection has been useful in several ways. It gives efficient polynomial time algorithms for several problems for which only non-constructive results were previously known. It also leads to several new structural results, such as tightness of the so-called determinant lower bound, and bounds on the discrepancy of union of set systems. In these lectures, we will study these results in detail and visit various concepts such as correlated brownian motion, non-constructive entropy method, gaussian roundings, sdp duality, Cauchy-Binet formula and so on.
Material:
Exercises: pdf
Diameter of polytopes and the Hirsch Conjecture
Francisco Santos, Universidad de Cantabria
The Hirsch Conjecture, posed in 1957, stated an upper bound of n-d for the maximum diameter of polytopes and polyhedra of dimension d with n facets. Although the conjecture itself has been disproved (in 1967 by Kee and Walkup for unbounded polyhedra and in 2010 by the lecturer for bounded polytopes) the underlying question ("How large can the diameter of a polytope be in terms of its dimension and number of facets?) is almost as open as before: no polynomial upper bound is known, and the counter-examples we have violate the conjecture by a mere 5%. In this course we first review the main classical results about diameters of polytopes (the d-step theorem, the proof of the Hirsch conjecture in several small or well-behaved cases, the counter-examples to related conjectures, such as the topological and monotone Hirsch conjectures). Then we explain the main ingredients that led to the recent counter-examples (analyzing the combinatorics of prismatoids via pairs of sphere maps, and the strong d-step theorem). In the last part we review the approaches to the polynomial Hirsch conjecture recently taken in Gil Kalai's polymath3 blog/wiki project.
Material:
Those interested in the counterexample to the Hirsch conjecture (although the course will be more about the context) can also look at:
Problems: pdf
Randomized pivoting rules for the simplex algorithm
Uri Zwick, Tel Aviv University
The simplex algorithm is one of the most widely used algorithms for solving linear programs in practice. It's worst case complexity, however, with essentially all known deterministic pivoting rules is exponential. There are, however, a randomized pivoting rule under which the expected running time of the simplex algorithm is subexponential.I will describe this pivoting rule, known as Random-Facet, discovered independently by Kalai and by Matousek, Sharir and Welzl, present the subexponential upper bound, and sketch a recent proof by Friedmann, Hansen and myself that shows that it is not polynomial. Several other randomized pivoting rules would also be discussed.
Material: The lecture will cover some material contained in the following papers, as well as additional material.
Problems: 2