Almost Optimal Pseudorandom Generators for Spherical Caps
Pravesh Kothari University of Texas at Austin, Email: Raghu Meka Email:
Abstract
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 $\epsilon$ and has an almost optimal seed-length of $O(\log n+\log(1/\epsilon)\cdot\log\log(1/\epsilon))$ . For an inverse-polynomially growing error $\epsilon$ , our generator has a seed-length optimal up to a factor of $O(\log\log{(n)})$ . The most efficient PRG previously known (due to Kane [34]) requires a seed-length of $\Omega(\log^{3/2}{(n)})$ in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution.
中文速览
针对高维空间中"半空间"（halfspace，即线性阈值函数）的伪随机生成器（pseudorandom generator，PRG）构造问题，以往最好的方案需要至少 Ω(log^{3/2} n) 比特的种子长度，距理论最优值仍有多对数因子的差距。本文提出了一种新的显式 PRG，对球面上的球帽（spherical cap）以误差 ε 进行欺骗，种子长度仅需 O(log n + log(1/ε)·log log(1/ε))，在多项式小误差情形下达到几乎最优，仅差一个 O(log log n) 因子。构造的核心思路是迭代降维：将权重向量依次投影到 √n、n^{1/4} 等维度，直至降至 O(log n) 维再做精确处理，每步投影只消耗 O(log(n/ε)) 个随机比特；而每步投影的"伪随机性"保证来自三个关键工具的结合——经典截断矩问题（truncated moment problem）的精细分析、近似正交设计（approximate orthogonal design）的显式构造，以及 Bourgain 和 Gamburd 关于李群中扩张性的奠基工作。这一结果几乎从根本上关闭了球面半空间 PRG 种子长度的长期开放问题，同时也为高斯分布下的半空间欺骗提供了类似的最优构造。
原文 arXiv:1411.6299;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1411.6299v2