tag:blogger.com,1999:blog-6555947.post8195884113651337188..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Hirsch Conjecture disprovedSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-9962964066739087562010-05-12T20:51:21.079-06:002010-05-12T20:51:21.079-06:00I knew it! I could bet that the conjecture is fal...I knew it! I could bet that the conjecture is false.<br /><br />The next step (which does have implications on simplex) is to find an example with super-polynomial diameter. Even that's probably doable.Mohammad Mahdianhttp://www.blogger.com/profile/08220570157337874429noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-85594582469778671352010-05-11T02:33:17.904-06:002010-05-11T02:33:17.904-06:00Hi Igor,
I'm not seeing any direct connectio...Hi Igor,<br /> I'm not seeing any direct connection between the Donoho/Tanner work and the Hirsch conjecture (true or false)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-81180803592421463832010-05-11T02:30:16.974-06:002010-05-11T02:30:16.974-06:00Suresh,
Dumb question:
Donoho and Tanner [1][2] h...Suresh,<br /><br />Dumb question:<br />Donoho and Tanner [1][2] have shown a deep connection between randomly projecting high dimensional polytopes to lower dimension subspaces and compressed sensing. Should we be expecting these computational phase transition results to be affected in any way as a result of this disproven conjecture ? From the previous comments, I would not expect a clear answer. What do you and your other readers think ?<br /><br />Cheers,<br /><br />Igor.<br /><br />[1] http://www.math.utah.edu/~tanner/CFRPP.pdf<br />[2] http://www.maths.ed.ac.uk/~tanner/DoTa_Finite.pdfIgorhttp://www.blogger.com/profile/17474880327699002140noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-50286934744903352512010-05-10T14:54:03.765-06:002010-05-10T14:54:03.765-06:00To expand a little - the conjecture is famous simp...To expand a little - the conjecture is famous simply due to the length of time that the question has remained open and the numerous partial results on the problem, but a counterexample doesn't lead directly to any new results. To quote Klee's paper on the problem, "finding a counterexample will be merely a small first step in the line of investigation related to the conjecture."<br /><br />The more general question of the polynomial Hirsch conjecture (whether polynomial diameter bounds exist for polytopes) may have more significance for linear programming, since a disproof might eliminate the possibility of polytime combinatorial LP algorithms, and upper bounds could lead to new polytime combinatorial LP algorithms.<br /><br />Of course, there's still no direct route from the polynomial conjecture to polynomial combinatorial linear programming algorithms either, so we're still several steps away from an answer there too.Anandhttp://www.blogger.com/profile/16850233492185797581noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43487996130191759132010-05-10T13:25:58.694-06:002010-05-10T13:25:58.694-06:00the funny thing is, probably not. While the conjec...the funny thing is, probably not. While the conjecture was famous in polytope theory and was motivated by the simplex, and LP algorithms in general, I don't think it has any kind of domino effect that I'm aware of. Being true didn't automatically imply a combinatorial p-time algorithm for linear programming.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-29243392872967264932010-05-10T13:22:52.203-06:002010-05-10T13:22:52.203-06:00Are there any significant results that depend on t...Are there any significant results that depend on the conjecture being true that will now have to be reconsidered?Anonymousnoreply@blogger.com