An invariance principle for polytopes

Let X be randomly chosen from {-1,1} n , and let Y be randomly chosen from the standard spherical Gaussian on R n . For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that |Pr[X ∈ P] - Pr[Y ∈ P]| ≤ log 8/5 k • Δ, where Δ is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known.

Authors

• Prahladh Harsha
• Adam R. Klivans
• Raghu Meka

Keywords

• noise sensitivity
• polytopes
• contingency tables
• pseudorandom generators
• limit theorems
• agnostic learning
• invariance principles
• average sensitivity