ELC Workshop on Exponential Lower Bounds for Pivoting Algorithms

March 24-25, CELC, Tokyo           (organized by ELC B01,B02)


  Please register here

Please note: Due to a medical emergency in his family, Oliver Friedmann had to return to Germany and will not be able to attend the workshop.
                          The workshop will go ahead with a modified schedule

 The search for a polynomial time pivoting rule for the simplex method is as old as the method itself. Klee and Minty showed in 1970
that Dantzig's original rule was exponential and similar results were soon found for most of the other known rules. All such lower
bound constructions were based on variations of the deformed hypercube and are defeated by the history based pivot rules of Cunningham,
Zadeh and others. These rules defied analysis for about 30 years until the recent work of Friedmann and others who constructed exponential
lower bounds based on results for parity games. These bounds apply to a wide variety of pivot based algorithms found, not only in linear
programming, but also Markov decision problems, stochastic games and acyclic unique sink orientations of hypercubes.

The bulk of this workshop is a tutorial on this subject starting from the beginning and ending with a number of challenging open problems.
No previous knowledge of the subject is assumed. The two days will be made as self-contained as possible for those who can only attend one day.
The first day will correspond roughly to the rightmost ellipse in the figure below and the second day to the remaining topics.

ELC members requiring travel expenses should contact the organizers

                                     

Tentative Schedule

3/24 (Tues) 
10:00-11:00 Lecture 1     Markhov decision problems(MDPs), linear programming and acyclic USOs
                                                 D. Avis(Kyoto)   slides   preprint1     preprint2    TCSwiki
11:15-12:15 Lecture 2     An exponential lower bound for MDPs, LPs and USOs using Cunninghams rule
                                                 D. Avis   slides
14:00-15:00 Lecture 3     On the sensitivity conjecture for Boolean functions
                                                 Xiaoming Sun (Chinese Academy of Science)   abstract
15:30-17:00                        Open problems & free discussion

18:00- dinner

3/25 (Wed)
10:00-10:50 Lecture 4     An FPTAS for the Volume Computationof 0-1 Knapsack Polytopes
                                                 Ei Ando (Sojo)    abstract

11:00-11:50 Lecture 5      Deterministic Random Walks for Rapidly Mixing Chains
                                                  Takeharu Shiraga (Kyushu)   abstract  

12:00-12:50 Lecture 6      Parity games, acyclic sink orientations of hypercubes, and other history based pivot rules.
                                                  D. Avis      slides  

14:00-17:00 open problems & free discussion
(Optional: excursion to Odaiba via Rainbow bridge, on foot, weather permitting)

Additional talks on this topic are welcome, please contact the organizers. 

                  
Organizers: David Avis (avis@i.kyoto-u.ac.jp)       Naoki Katoh (naoki@archi.kyoto-u.ac.jp)