SupplementaryMaterial

Wecan also assumeE tobe the ℓ2 unit ball; otherwise, just apply an appropriate affine transformation at the beginning of the proof, and itsinverse atthe end. For the running time, theforloops performk niterations, and thewhileloop performs at mostn iterations as each iteration strictly decreases the size ofX. The running time of any iteration is dominated by the computation ofMVE(Si) or MVE(Xi), which takes time poly(n+m),seeabove.Hence Round(X,k)runsintimepoly(n+m). Thesecondobstacle isthat, in order for hit-and-run to be efficient, we must haveasystem of coordinates under which Vi is well-rounded, i.e., not "too thin" along any direction. Unfortunately, lettingVi+1 = Vi Zi may makeVi+1 extremely thin, as we haveno control overZi (it depends on theSEEDanswers).