Plans for polymath3

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?)


This entry was posted in Convex polytopes, Polymath3 and tagged , . Bookmark the permalink.

4 Responses to Plans for polymath3

  1. Pingback: Polymath on other blogs « The polymath blog

  2. Pingback: Polymath3 « Euclidean Ramsey Theory

  3. Anand says:

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

  4. Gil says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s