[METRIC 2011] Adam Klivans
- il y a 13 ans
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 25, 13:30-14:30 - Adam Klivans (U. Texas, Austin)
Invariance principles for polytopes
----
Let X be randomly chosen from {-1,1}^n, and let Y be randomly chosen from a standard n-variate Gaussian. For any polytope P formed by the intersection of k halfspaces, we prove that | Pr [X \in P] - Pr [Y \in P] | \leq polylog(k) * \Delta, where \Delta 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. We give two important applications of our main result:
1) A bound of polylog(k) * \eps^{O(1)} on the noise sensitivity of intersections of k regular halfspaces (previous work gave bounds linear in k). This gives the first quasipolynomial-time algorithm for learning intersections of regular halfspaces over the hypercube.
2) The first pseudorandom generators (with polylogarithmic seed length) for regular polytopes. This gives a deterministic algorithm for approximately counting the number of solutions to a broad class of integer programs (including dense covering programs and contingency tables).
Joint work with Prahladh Harsha and Raghu Meka.
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 25, 13:30-14:30 - Adam Klivans (U. Texas, Austin)
Invariance principles for polytopes
----
Let X be randomly chosen from {-1,1}^n, and let Y be randomly chosen from a standard n-variate Gaussian. For any polytope P formed by the intersection of k halfspaces, we prove that | Pr [X \in P] - Pr [Y \in P] | \leq polylog(k) * \Delta, where \Delta 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. We give two important applications of our main result:
1) A bound of polylog(k) * \eps^{O(1)} on the noise sensitivity of intersections of k regular halfspaces (previous work gave bounds linear in k). This gives the first quasipolynomial-time algorithm for learning intersections of regular halfspaces over the hypercube.
2) The first pseudorandom generators (with polylogarithmic seed length) for regular polytopes. This gives a deterministic algorithm for approximately counting the number of solutions to a broad class of integer programs (including dense covering programs and contingency tables).
Joint work with Prahladh Harsha and Raghu Meka.