Fooling Thresholds of Halfspaces

Minglong Qin; Penghui Yao; Mingnan Zhao; Haigang Zhou

In the authors' words

We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $δ$ -fools every $k$ -out-of- $m$ threshold of $m$ halfspaces over ${- 1, 1}^{n}$ with seed length $O (κ^{6 + 2 ε} lo g^{6 + 2 ε} m \cdot δ^{- (2 + 2 ε)} lo g n)$ , for any arbitrarily small constant $ε > 0$ , where $κ = min {k, m - k + 1}$ . The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.

Main resultThe abstract does not state a limitation.

Fooling Thresholds of Halfspaces

In the authors' words

More on Algorithms & complexity that day

Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

Dynamic Contention Resolution Schemes

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

TokaGLINT: A Scalable GPU-Tailored Implicit Solver for Full 3D Tokamak Electromagnetic Simulations