Markov Chains and Polynomial Time Algorithms

This paper outlines the use of rapidly mixing Markov Chains in randomized polynomial time algorithms to solve approximately certain counting problems. They fall into two classes: combinatorial problems like counting the number of perfect matchings in certain graphs and geometric ones like computing the volumes of convex sets. >

Authors

• Ravindran Kannan

Keywords

• Polynomials
• Steady-state
• Lattices
• Sampling methods
• Approximation algorithms
• Computer science
• Upper bound
• Convergence
• Markov Chain
• Polynomial-time Algorithm
• Perfect Match
• Convex Set
• Combinatorial Problem
• Rapid Mixing
• Graph Matching
• Counting Problem
• Steady State
• Random Walk
• General Setting
• Uniform Density
• Mixing Time
• Intensive Setting
• Current Point
• Transition Probability Matrix
• Hair Color
• Area In Fig
• Sampling Problem
• Steady-state Probability
• Row Sums
• Ball Of Radius
• Eye Color
• Column Sums
• Polytope
• Integer Lattice
• Sharp Corners
• Toy Example
• Total Variation Distance