Sachdeva, SushantVishnoi, Nisheeth K.2016-11-212016-11-212016-11-21201610.1016/j.orl.2016.07.005https://infoscience.epfl.ch/handle/20.500.14299/131497WOS:000384854700013We study the mixing time of the Dikin walk in a polytope a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing time are important for algorithms for sampling and optimization over polytopes. Here, we provide a simple proof of their result that this random walk mixes in time O(mn) for an n-dimensional polytope described using m inequalities. (C) 2016 Elsevier B.V. All rights reserved.PolytopesSamplingVolume computationRandom walksInterior point methodstext::journal::journal article::research article