Monthly Archives: May 2010

Test Your Intuition (12): Perturbing a Polytope

Posted on May 12, 2010 by Gil Kalai

Let P be a d-dimensional convex polytope. Can we always perturb the vertices of P moving them to points with rational coordinates without changing the combinatorial structure of P? In order words, you require that a set of vertices whose … Continue reading →

Posted in Convex polytopes, Test your intuition | Tagged , | 4 Comments

Francisco Santos Disproves the Hirsch Conjecture

Posted on May 10, 2010 by Gil Kalai

A title and an abstract for the conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” drew a special attention: Title: “A counter-example to the Hirsch conjecture” Author: Francisco Santos, Universidad de Cantabria Abstract:  I have been in … Continue reading →

Posted in Convex polytopes, Open problems, Polymath3 | 37 Comments

Drunken Time and Drunken Computation

Posted on May 4, 2010 by Gil Kalai

The problem We are used to computer programs or models for computations that perform at time  step , .  Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time  step , where … Continue reading →

Posted in Computer Science and Optimization | 10 Comments