Seminar: April 6, 2009

Mark Braverman, Microsoft Research

Poly-logarithmic Independence Fools AC0 Circuits

Let K be a polytope in R^n defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first to have a mixing time that is strongly polynomial when started from a ``central'' point x. If s is the supremum over all chords pq passing through x of |p-x|/|q-x| and \epsilon is an upper bound on the desired total variation distance from the uniform, it is sufficient to take O(m n( n log (s m) + log 1/\epsilon)) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to approximately solve linear programs with high probability in polynomial time. The fact that this algorithm has a run-time that is provably polynomial is notable since the run-time of the analogous deterministic affine algorithm analyzed by Dikin has no known polynomial guarantees. This is work with Ravi Kannan.