The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof

Nisheeth K. Vishnoi; Sushant Sachdeva

The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1508.01977 v2 pith:VT7YG55F submitted 2015-08-09 cs.DS math.OC

Sushant Sachdeva , Nisheeth K. Vishnoi This is my paper · ORCID

classification cs.DSmath.OC

keywords walktimemixingpolytopedikinproofrandomsimple

verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments

read the original abstract

We 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

PolytopeWalk: Sparse MCMC Sampling over Polytopes
stat.CO 2024-12 conditional novelty 5.0 of 10

PolytopeWalk is a sparse, constrained-form MCMC library for uniform polytope sampling that reports faster per-step runtimes than the Volesti package on benchmark polytopes.

Pith tools