Search Results for: Hirsch

Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture

This post is authored by Karim Adiprasito The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction.  Jesus de Loera and Steve Klee described simplicial polytopes which are not  … Continue reading

Posted in Convex polytopes, Guest blogger | Tagged , , , | Leave a comment

Some Updates

Jeff Kahn was in town: so we worked together also with Ehud Friedgut and Roy Meshulam (and others) quite intensively. Very nice! Stay tuned for a report! Polynomial Hirsch conjecture (polymath3): While the conjecture remains wide open there are some … Continue reading

Posted in Updates | 3 Comments

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 … Continue reading

Posted in Computer Science and Optimization, Conferences, Guest blogger | Tagged | 4 Comments

IPAM Remote Blogging: Santos-Weibel 25-Vertices Prismatoid and Prismatoids with large Width

Here is a web page by Christope Weibel on the improved counterexample. The IPAM webpage contains now slides of some of the lectures. Here are Santos’s slides. The last section contains some recent results on the “width of 5-prismatoids”  A prismatoid is a polytope … Continue reading

Posted in Computer Science and Optimization, Conferences, Convex polytopes | 2 Comments

Is Backgammon in P?

  The Complexity of Zero-Sum Stochastic Games with Perfect Information Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is … Continue reading

Posted in Computer Science and Optimization, Games, Open problems, Probability | 9 Comments

Emmanuel Abbe: Erdal Arıkan’s Polar Codes

Click here for the most recent polymath3 research thread. A new thread is comming soon. Emmanuel Abbe and Erdal Arıkan This post is authored by Emmanuel Abbe A new class of codes, called polar codes, recently made a breakthrough in … Continue reading

Posted in Information theory, Probability | Tagged , | 17 Comments

Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Click here for the most recent polymath3 research thread. I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago Suppose that  is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . … Continue reading

Posted in Combinatorics, Open problems | Tagged , , , , , | 9 Comments

János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Click here for the most recent polymath3 research thread. Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach. This post is authored by János Pach A … Continue reading

Posted in Combinatorics, Geometry, Guest blogger, Open problems | Tagged , | 13 Comments

Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading

Posted in Computer Science and Optimization, Convex polytopes, Games | Tagged , | 11 Comments

Budapest, Seattle, New Haven

Here we continue the previous post on Summer 2010 events in Reverse chronological order. Happy birthday Srac In the first week of August we celebrated Endre Szemeredi’s birthday. This was a very impressive conference. Panni, Endre’s wife, assisted by her … Continue reading

Posted in Blogging, Conferences | Tagged , , , | 6 Comments