Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)

Scanned letter by Zadeh. (c) Günter M. Ziegler

left-to-right: David Avis, Norman Zadeh,  Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim.

Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for most presentations.

This post is authoured by Günter Ziegler with some help by David Avis. A German (slightly expanded) version can be found on Günter’s blog.

Oliver Friedmann, a Computer Science graduate student at Munich University, will defend his thesis next month. It contains a proof, that “Zadeh’s rule” for linear optimization is “exponential”, that is, it may take an awfully long time on relatively small problems.

 

Why is this remarkable?

“Linear Optimization” problems are extremely important computational tasks that arise in all kinds of larger planning processes. Such tasks are usually solved on a computer using a method known as the “simplex algorithm”, invented by George Dantzig in 1947. The simplex method needs a prescription for making local choices in its search, known as the “pivot rule”. And it is known about mostsuch pivot rules that they can be extremely slow and inefficient on particular optimization problems. One would like (and need) a rule that is “provably fast”.

One candidate for this was the “Zadeh rule” — until today. When Zadeh was a postdoc in the Department of Operations Research at Stanford he published a technical report on the worst case examples of the simplex method. This was never published in a journal, but became part of the folklore of mathematical programming. It is now available at http://www.stanford.edu/group/SOL/reports/OR-80-27.pdf and was reprinted in Polyhedral Combinatorics, CRM-AMS Proceedings, pp 131-144, 2009. In this report, among other things, he described the ‘least entered rule’ which was the first of many history based rules for the simplex method, none of which had been shown to run in super-polynomial time until now. David Avis’s lecture at IPAM is devoted to history based rules for acyclic USOs.

Around that time, when Zadeh was not yet rich, he had promised 1000$ for anyone who could prove that the rule he had proposed was slow — or for a proof that it was always fast. This is documented in a handwritten letter to Victor Klee, professor of mathematics at the University of Washington in Seattle:

The schedule of a workshop at IPAM, the “Institute for Pure and Applied Mathematics” at UCLA (University of California at Los Angeles) announces a main lecture by Oliver Friedmann for Thursday, January 20, 10:30 am, where he will present his solution to the problem — Zadeh’s rule is slow in general. Norm Zadeh has announced that he will come to UCLA, attend the talk, and produce a 1000$ check for Oliver Friedmann.

Who is Norman Zadeh?

(Here is the wikipedia article.)  Norman  is the son of Lofti Zadeh who got famous as the inventor “Fuzzy Logic”. He got a Ph.D. in Berkeley, then he was a Postdoc and faculty member at Stanford, Columbia, UC Irvine and UCLA. At some point he left Mathematics, became a professional poker player, got extremely wealthy (just recently he sold his Beverly Hills villa for more than 16 Million Dollars), and now for many years has been working in an industry that produces glossy photos of beautiful (naked) women.
His most prominent product is a magazine and website called “Perfect 10”. … so clearly this is a quite unusual career for a Mathematician …

Money time at IPAM

Oliver Friedman’s research paper is brand new, so in particular the experts have not checked his solution to Zadeh’s problem in detail. However, this week it was accepted to be presented at the renowned IPCO Conference 2011 So, the jury is still out — and until Friedmann’s solution has been verified in detail and accepted for publication in a research journal, the check for Oliver Friedman will be held by Günter M. Ziegler, in his function as the former president of the German Mathematical Society, who also gave a main lecture on “bad linear programs” at the UCLA workshop…

Oliver Friedmann, (picture: Eddie Kim)

Günter M. Ziegler
http://www.math.tu-berlin.de/~ziegler/presse.shtml