2012 Tucker Prize Citation
The Tucker Prize for an outstanding doctoral thesis has been awarded to Oliver
Friedmann, Department of Computer Science, LudwigMaximiliansUniversität in Munich,
Germany, for his thesis: Exponential Lower Bounds for Solving Infinitary Payoff Games and
Linear Programs.
One of the most prominent mysteries in Optimization is the question of whether a linear
program can be solved in stronglypolynomial time. A strongly polynomialtime method would
be polynomial in the dimension and in the number of inequalities only, whereas the
complexity of the known weaklypolynomial time algorithms for linear programming, like the
ellipsoid method or variants of the interiorpoint method, also depend on the binary
encoding length of the input. The simplex method, though one of the oldest methods for
linear programming, still is a candidate for such a strongly polynomial time algorithm. This
would require the existence of a pivoting rule that results in a polynomial number of pivot
steps. Since the famous KleeMinty example, many techniques for deriving exponential lower
bounds on the number of iterations for particular pivoting rules have been found.
Some very important pivoting rules, however, have resisted a superpolynomial lowerbound
proof for a very long time. Among them the RandomFacet pivoting rule and Zadeh's pivoting
rule. RandomFacet has been shown to yield subexponential running time of the
simplex method independently by Kalai as well as by Matousek, Sharir and Welzl.
Zadeh was a postdoc at Stanford in 1980, when he published a technical report with his
leastentered rule: enter the improving variable that has been entered least often. In a
handwritten letter to Viktor Klee he offered $1000 to the person who either showed this
rule to be a polynomial pivoting rule for the simplex method, or provided a counterexample
to it being a polynomial method. Consequently, Zadeh's rule is very well known in the
linearprogramming community.
In his thesis, Oliver Friedmann has shown superpolynomial lower bounds for pivoting rules
in a groundbreaking way. The novelty of his approach is to establish a connection from
policy iteration for 2player parity games and Markov decision processes to pivoting in
linear programs. In his paper Subexponential lower bounds for randomized pivoting rules for
solving linear programs, coauthored with Hansen and Zwick (Proceedings of the 43rd ACM
Symposium on Theory of Computing, STOC'11, San Jose, CA, USA, 2011), Friedmann shows a
superpolynomial bound on the RandomFacet pivoting rule. This paper was awarded the
prestigious STOC best paper award. This line of work, initiated by Friedmann, shows that the
standard strategy iteration algorithm for parity games may require an exponential number of
iterations. By giving analogous results for Markov decision processes, Friedmann extends
superpolynomial lower bounds to pivoting in linear programming.
The thesis of Friedmann lays out this connection of improvement strategies for games and
pivoting. Two of the most prominent results are the aforementioned lower bounds for
RandomFacet and Zadeh's rule. But, with this new connection, other pivoting rules that
resisted superpolynomial lowerbound proofs have also been shown to be nonpolynomial, like
the RandomEdge rule and, in a recent publication of Friedmann, Cunningham's rule as well.
Oliver Friedmann is 27 years old (at the date of receiving the Tucker Prize). His
undergraduate, master'slevel and Ph.D. degrees were all undertaken in the Department of
Computer Science at the LudwigMaximiliansUniversität in Munich, and were completed in
2006, 2008 and 2011 respectively. His Ph.D. thesis was completed in only 2.5 years under
supervision from Martin Hofmann and Martin Lange.
With his thesis, Friedmann has built bridges between sofar seemingly unrelated fields,
enriched optimization with novel ideas and techniques and achieved groundbreaking results
that settled many longstanding open problems. This thesis truly deserves to be awarded with
the Tucker Prize 2012.
The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee are
Amitabh Basu and Guanghui Lan.
Amitabh Basu obtained his undergraduate degree in Computer Science and
Engineering from the Indian Institute of Technology, Delhi in 2004, and received an M.S. in
Computer Science from Stony Brook University in 2006. In May 2010, he finished a Ph.D. in
Algorithms, Combinatorics and Optimization from the Tepper School of Business, Carnegie
Mellon University advised by G&eactue;rard Cornuéjols. He is currently a visiting assistant
professor in the Department of Mathematics at the University of California, Davis.
The thesis of Basu, entitled Corner Polyhedra and Maximal Latticefree Convex Sets: A
Geometric Approach to Cutting Planes, studies the properties of cutting planes
generated from several rows of the simplex tableau, in the context of solving mixed integer
linear programming problems. This new research direction is a big departure from earlier
investigations in the theory of cutting planes such as the study of mixed integer cuts and
split cuts, which can be generated by integrality arguments applied to a single equation.
A very interesting and promising result in the thesis is the comparison of the strength of
the new cuts generated from two rows of the simplex tableau to the strength of the old
cuts. Basu shows that the new cuts can be arbitrarily stronger. The thesis also revisits the
foundations of cutting plane theory, studying links between cutting planes and maximal
latticefree convex sets, and gives a counterexample to a famous conjecture of Gomory and
Johnson about the facets of the group polyhedron. An important result about lifting integer
variables is also presented in the thesis.
Today, the most successful solvers for integer programming problems use cutting planes
generated from one row of the simplex tableau and lifting techniques. The results from
Basu's thesis open the way to the next generation of improvements in solvers, based on
cutting planes generated from several rows of the simplex tableau.
Guanghui Lan obtained his undergraduate degree in Mechanical Engineering
from the Xiangtan University, China, in 1996 and went on to complete two master's degrees,
one in Mechanical Engineering at the Shanghai Jiao Tong University, China, 1999, and the
other in Industrial Engineering at the University of Louisville, Kentucky, 2004. In January
2009 he completed his Ph.D. in Industrial and Systems Engineering at Georgia Institute of
Technology supervised by Arkadi Nemirovski and coadvised by Renato Monteiro and Alexander
Shapiro. He is currently an Assistant Professor of Industrial and Systems Engineering at the
University of Florida.
Lan's dissertation, entitled Convex Optimization under Inexact FirstOrder Information,
concerns the design and complexity analysis of firstorder methods for solving convex
optimization problems under a stochastic oracle. This includes several important classes of
convex programming problems, such as general nonsmooth problems, composite optimization
problems whose objective functions are sums of smooth and nonsmooth components, and
problems whose feasible regions consist of simple compact convex sets intersected with
affine manifolds. The novel methods proposed are accompanied by a worstcase
iterationcomplexity analysis. New complexity results are also given for deterministic
methods in the presence of inexact gradients.
The impact of finetuned optimal methods for convex optimization on actual computation is
prominent and significant. The outstanding contribution of Lan's thesis is an optimal method
for stochastic composite optimization which closes the gap between the convergence rate of
existing firstorder methods and the theoretically optimal rate of convergence. It
represents the first universally optimal method which covers smooth, nonsmooth and
stochastic convex programming as special cases and overcomes the need to handle different
classes of convex optimization problems using different (sub)optimal methods. Remarkably,
the optimal rate of convergence had not been attained before even for the deterministic
case.
