2012 Tucker Prize Citation
The Tucker Prize for an outstanding doctoral thesis has been awarded to Oliver
Friedmann, Department of Computer Science, Ludwig-Maximilians-Universität in Munich,
Germany, for his thesis: Exponential Lower Bounds for Solving Infinitary Payoff Games and
One of the most prominent mysteries in Optimization is the question of whether a linear
program can be solved in strongly-polynomial time. A strongly polynomial-time method would
be polynomial in the dimension and in the number of inequalities only, whereas the
complexity of the known weakly-polynomial time algorithms for linear programming, like the
ellipsoid method or variants of the interior-point 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 Klee-Minty 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 super-polynomial lower-bound
proof for a very long time. Among them the Random-Facet pivoting rule and Zadeh's pivoting
rule. Random-Facet has been shown to yield sub-exponential 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
least-entered rule: enter the improving variable that has been entered least often. In a
hand-written 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
In his thesis, Oliver Friedmann has shown super-polynomial lower bounds for pivoting rules
in a groundbreaking way. The novelty of his approach is to establish a connection from
policy iteration for 2-player 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
super-polynomial bound on the Random-Facet 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
super-polynomial 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
Random-Facet and Zadeh's rule. But, with this new connection, other pivoting rules that
resisted super-polynomial lower-bound proofs have also been shown to be non-polynomial, like
the Random-Edge 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's-level and Ph.D. degrees were all undertaken in the Department of
Computer Science at the Ludwig-Maximilians-Universitä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 so-far 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 Lattice-free 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
lattice-free 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 co-advised 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 First-Order Information,
concerns the design and complexity analysis of first-order methods for solving convex
optimization problems under a stochastic oracle. This includes several important classes of
convex programming problems, such as general non-smooth problems, composite optimization
problems whose objective functions are sums of smooth and non-smooth components, and
problems whose feasible regions consist of simple compact convex sets intersected with
affine manifolds. The novel methods proposed are accompanied by a worst-case
iteration-complexity analysis. New complexity results are also given for deterministic
methods in the presence of inexact gradients.
The impact of fine-tuned 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 first-order methods and the theoretically optimal rate of convergence. It
represents the first universally optimal method which covers smooth, non-smooth 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