Search Results for: Hirsch

Is Backgammon in P?

Posted on January 14, 2011 by

  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

Posted on November 25, 2010 by

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

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

Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Posted on November 24, 2010 by

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

Posted on November 20, 2010 by

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!

Posted on November 9, 2010 by

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

Posted on October 15, 2010 by

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

Polymath Reflections

Posted on March 17, 2010 by

Polymath is a collective open way of doing mathematics. It  started over Gowers’s blog with the polymath1 project that was devoted to the Density Hales Jewett problem. Since then we  had Polymath2 related to Tsirelson spaces in Banach space theory , an  intensive Polymath4 devoted … Continue reading →

Posted in Mathematics over the Internet, Open discussion | 2 Comments

Plans for polymath3

Posted on December 8, 2009 by

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

Posted in Convex polytopes, Polymath3 | Tagged , | 4 Comments

Mathematics, Science, and Blogs

Posted on January 28, 2009 by

Michael Nielsen wrote a lovely essay entitled “Doing science online” about  mathematics, science,  and blogs. Michael’s primary example is a post over Terry Tao’s blog about the Navier-Stokes equation and he suggests blogs as a way of scaling up scientific conversation. Michael is writing … Continue reading →

Posted in Blogging, What is Mathematics | Tagged , , , , | 5 Comments

Telling a Simple Polytope From its Graph

Posted on January 16, 2009 by

Peter Mani  (a photograph by Emo Welzl) Simple polytopes, puzzles   Micha A. Perles conjectured in the ’70s that the graph of a simple -polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind … Continue reading →

Posted in Convex polytopes, Open problems | Tagged , , | 4 Comments