Polymath3 is planned to study the polynomial Hirsch conjecture. In order not to conflict with Tim Gowers’s next polymath project which I suppose will start around January, I propose that we will start polymath3 in **mid April 2010**. I plan to write a few posts on the problem until then. We had a long and interesting discussion regarding the Hirsch conjecture followed by another interesting discussion. We can continue the discussion here.

One direction which I see as promising is to try to examine the known upper and lower bounds for the abstract problem. Here is again a link for the paper Diameter of Polyhedra: The Limits of Abstraction by Freidrich Eisenbrand, Nicolai Hahnle, Sasha Razborov, and Thomas Rothvoss.

I would also be happy to hear your thoughts about strong polynomial algorithms for linear programming either via randomised pivot rules for the simplex algorithm or by any other method. It occured to me that I am not aware of any work trying to examine the possibility that there is no strongly polynomial algorithm for linear programming. Also I am not aware of any work which shows that strongly polynomial algorithm for LP is a consequence of some (however unlikely) computational assumption. (Is it a consequence of NP=P? of P=P-space?)

### Like this:

Like Loading...

*Related*

Pingback: Polymath on other blogs « The polymath blog

Pingback: Polymath3 « Euclidean Ramsey Theory

Just curious; is the formal launch of polymath3 going to be different in structure from the previous two discussions?

Dear Anand, I suppose it will be similar. At the time, the discussion slowed down and there was another polymath running in parallel. I dont know if it will get off the ground on April but we will try.