Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala

Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a give…