TY - GEN
T1 - Almost optimal pseudorandom generators for spherical caps
AU - Kothari, Pravesh K.
AU - Meka, Raghu
N1 - Publisher Copyright:
© Copyright 2015 ACM.
PY - 2015/6/14
Y1 - 2015/6/14
N2 - Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing pseudorandom generators (PRGs) for halfspaces over the sphere, aka spherical caps, which besides being interesting and basic geometric objects, also arise frequently in the analysis of various randomized algorithms (e.g., randomized rounding). We give an explicit PRG which fools spherical caps within error e and has an almost optimal seed-length of O(logn + log(1/∈) ·loglog(1/∈)). For an inverse-polynomially growing error ∈, our generator has a seed-length optimal up to a factor of O(loglog (n)). The most efficient PRG previously known (due to Kane [31]) requires a seed-length of Ω(log3/2 (n)) in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution. Our construction and analysis are significantly different from previous works on PRGs for halfspaces and build on the iterative dimension reduction ideas of [45, 9], the classical moment problem from probability theory and explicit constructions of approximate orthogonal designs based on the seminal work of Bourgain and Gamburd [6] on expansion in Lie groups.
AB - Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing pseudorandom generators (PRGs) for halfspaces over the sphere, aka spherical caps, which besides being interesting and basic geometric objects, also arise frequently in the analysis of various randomized algorithms (e.g., randomized rounding). We give an explicit PRG which fools spherical caps within error e and has an almost optimal seed-length of O(logn + log(1/∈) ·loglog(1/∈)). For an inverse-polynomially growing error ∈, our generator has a seed-length optimal up to a factor of O(loglog (n)). The most efficient PRG previously known (due to Kane [31]) requires a seed-length of Ω(log3/2 (n)) in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution. Our construction and analysis are significantly different from previous works on PRGs for halfspaces and build on the iterative dimension reduction ideas of [45, 9], the classical moment problem from probability theory and explicit constructions of approximate orthogonal designs based on the seminal work of Bourgain and Gamburd [6] on expansion in Lie groups.
KW - Halfspaces
KW - Orthogonal designs
KW - Pseudorandom Generators
UR - http://www.scopus.com/inward/record.url?scp=84958756824&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958756824&partnerID=8YFLogxK
U2 - 10.1145/2746539.2746611
DO - 10.1145/2746539.2746611
M3 - Conference contribution
AN - SCOPUS:84958756824
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 247
EP - 256
BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015
Y2 - 14 June 2015 through 17 June 2015
ER -