Complexity of Games, Polyhedra and Lattice Points

May 17-19, 2006, FIM, ETH Zurich, Switzerland

May 17 (Wednesday)
08:50-09:00 Opening  
Session 1-1 HG G 19 [Welzl]
09:00-10:00 Daniel Spielman A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
10:30-11:30 Uli Wagner A Geometric Generalization of the Upper Bound Theorem
Session 1-2 HG G 19 [Fukuda]
11:40-12:40 Shmuel Onn Convex Integer Optimization and Universality of Multiway Polytopes
Session 1-3 HG G 19 [Lüthi], Memorial Session for Carl E. Lemke
14:30-15:30 Bernhard von Stengel Geometric Views of Linear Complementarity Algorithms and Their Complexity
16:00-17:00 Edith Elkind The Computational Complexity of Finding a Nash Equilibrium
17:30 Apero, HG G 43 Hosted by FIM
May 18 (Thursday)
Session 2-1 HG G 19 [Fukuda]
09:00-10:00 Michel Las Vergnas Fully optimal bases in linear programming, the active bijection, and application
10:30-11:30 Endre Boros Enumerating vertices of polyhedra and related generating problems
Session 2-2 HG G 19 [von Stengel], Memorial Session for Carl E. Lemke
11:40-12:40 Tibor Szabo Making vs. Avoiding in Positional Games
14:30-15:30 Jong-Shi Pang Applications of Nash Equilibria and Lemke's Method in Electricity Market
Session 2-3 HG G 19 [Lüthi]
16:00-17:00 Yurii Nesterov Polynomial technique in combinatorial optimization
18:45 Banquet Restaurant UTO KULM (
  Joseph Ecker Remembering C.E. Lemke
May 19 (Friday)
Session 3 HG G 19 [Onn]
09:00-10:00 Alexander Barvinok Enumeration of contingency tables and integer flows
10:30-11:30 Pavel Valtr On The Empty Hexagon Theorem
11:40-12:20 Gyula Karolyi Discrepancy of lattice points in round convex bodies


Invited speakers' table is reserved at Dozentenfoyer, a restaurant at the top of the main

building HG from about 12:45 to 14:00. You have to pay yourself.


Building HG = the main building of ETH Zurich

A map of ETH Zentrum campus can be found in .


FIM (Institute for Mathematical Research), ETH Zurich

with additional support by

Institute for Operations Research (IFOR), ETHZ and

Theory of Combinatorial Algorithm Group, ETHZ


Imre Bárány,

Komei Fukuda,

Hans-Jakob Lüthi,

Emo Welzl,

Komei Fukuda 2006-05-25