Almost Optimal Pseudorandom Generators for Spherical Caps
Almost Optimal Pseudorandom Generators for Spherical Caps
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 …