Explicit pseudorandom generators fool threshold functions of halfspaces
Fooling Thresholds of Halfspaces
Computational Complexity
Summary
Some functions used in computer science make decisions based on many yes/no conditions, called halfspaces. The paper shows how to build special random-like input sequences that trick these functions into thinking the input is random, even when it isn’t. The authors use advanced math tools to create and analyze these input sequences efficiently for a broad class of such decision functions. This helps understand the complexity of these functions and their behavior under randomness.
What this means in practice
- •For machine learning engineers: Design algorithms that better learn threshold-based models under uniform and Gaussian input distributions using new noise sensitivity and surface area bounds.
- •For cryptographic protocol designers: Create efficient pseudorandom input sequences that reliably fool complex threshold-based systems relevant in secure computation and complexity theory.
A theory result. No direct application yet.
Authors
Minglong Qin, Penghui Yao, Mingnan Zhao, Haigang Zhou
Abstract
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 $\widetilde{O}(κ^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdotδ^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>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.