  In Friedmann, Hansen, and Zwick (2011) we claimed that the expected number of
pivoting steps performed by the Random-Facet algorithm of Kalai and of
Matousek, Sharir, and Welzl is equal to the expected number of pivoting steps
performed by Random-Facet^*, a variant of Random-Facet that bases its random
decisions on one random permutation. We then obtained a lower bound on the
expected number of pivoting steps performed by Random-Facet^* and claimed that
the same lower bound holds also for Random-Facet. Unfortunately, the claim that
the expected numbers of steps performed by Random-Facet and Random-Facet^* are
the same is false. We provide here simple examples that show that the expected
numbers of steps performed by the two algorithms are not the same.
