Access Restriction

Author Harsha, Prahladh ♦ Klivans, Adam ♦ Meka, Raghu
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Invariance ♦ Agnostic learning ♦ Intersection of halfspaces ♦ Noise sensitivity ♦ Polytopes ♦ Pseudorandomness
Abstract Let $\textit{X}$ be randomly chosen from ${-1,1}^{n},$ and let $\textit{Y}$ be randomly chosen from the standard spherical Gaussian on $ℝ^{n}.$ For any (possibly unbounded) polytope $\textit{P}$ formed by the intersection of $\textit{k}$ halfspaces, we prove that $|Pr[\textit{X}$ ∈ $\textit{P}]$ - $Pr[\textit{Y}$ ∈ $\textit{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 $\textit{k}.$ Previously, only bounds that were at least linear in $\textit{k}$ were known. The proof of the invariance principle is based on a generalization of the Lindeberg method for proving central limit theorems and could be of use elsewhere. We give two important applications of our invariance principle, one from learning theory and the other from pseudorandomness. (1) A bound of $log^{O(1)}k$ ṡ $ε^{1/6}$ on the Boolean noise sensitivity of intersections of $\textit{k}$ “regular” halfspaces (previous work gave bounds linear in $\textit{k}).$ This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces. (2) A pseudorandom generator (PRG) for estimating the Gaussian volume of polytopes with $\textit{k}$ faces within error Δ and seed-length $\textit{O}(log$ $\textit{n}$ poly(log $\textit{k},1/Δ)).$ We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-01-09
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 59
Issue Number 6
Page Count 25
Starting Page 1
Ending Page 25

Open content in new tab

   Open content in new tab
Source: ACM Digital Library