A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions

Penghui Yao, Mingnan Zhao · 2025

Read A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions by Penghui Yao, Mingnan Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10904.txt.

Introduction

Penghui Yao and Mingnan Zhao built in 2025 a fake-random generator that fools a broad class of decision functions. The functions combine a few low-degree polynomial threshold rules, the workhorses behind simple classifiers. A good generator stretches a short truly random seed into output no such function can tell from real randomness.

Their recipe sums a modest number of random Gaussian vectors matched on many moments, then discretizes. The seed stays short even as inputs grow. Small seeds mean fast derandomization, turning randomized algorithms into certain ones for this function family.

Catalog record

CREATORPenghui Yao, Mingnan Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10904

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions Penghui Yao, Mingnan Zhao Abstract Developing explicit pseudorandom generators (PRGs) for prominent categories of Boolean functions is a key focus in computational complexity theory. In this paper, we investigate the PRGs against the functions of degree- d d polynomial threshold functions (PTFs) over Gaussian space. Our main result is an explicit construction of PRG with seed length poly ⁡ ( k , d , 1 / ϵ ) ⋅ log ⁡ n \mathrm{poly}\!\left(k,d,1/\epsilon\right)\cdot\log n that can fool any function of k k degree- d d PTFs with probability at least 1 − ε 1-\varepsilon . More specifically, we show that the summation of L L independent R R -moment-matching Gaussian vectors ϵ \epsilon -fools functions of k k degree- d d PTFs, where L = poly ⁡ ( k , d , 1 ϵ ) L=\mathrm{poly}\!\left(k,d,\frac{1}{\epsilon}\right) and R = O ⁡ ( log ⁡ k ​ d ϵ ) R=O({\log\frac{kd}{\epsilon}}) . The PRG is then obtained by applying an appropriate discretization to Gaussian vectors with bounded independence. 1 Introduction In computational complexity theory, derandomization is a powerful technique that aims to reduce randomness in algorithms without sacrificing efficiency or accuracy. A versatile approach for derandomization is to design explicit pseudorandom generators (PRGs) for notable families of Boolean functions. A PRG for a family of Boolean functions is able to consume few random bits and produce a distribution over high-dimensional vectors, which is indistinguishable from a target distribution, such as the uniform distribution over Boolean cube, by any function in the family. In this paper, we concern ourselves with the Gaussian distribution over \mathbb{R}^{n} . Formally, Definition 1.1 . Let \mathcal{F}\subseteq\left\{f:\mathbb{R}^{n}\to\{0,1\}\right\} be a family of Boolean functions. A function G:\{0,1\}^{r}\to\mathbb{R}^{n} is a pseudorandom generator for \mathcal{F} with error \epsilon over Gaussian distribution \mathcal{N}\left(0,1\right)^{n} if for any f\in\mathcal{F} , \left|\E_{\begin{subarray}{c}s\sim_{u}\left\{0,1\right\}^{r}\end{subarray}}\!\left[f(G(s))\right]-\E_{\begin{subarray}{c}x\sim\mathcal{N}\left(0,1\right)^{n}\end{subarray}}\!\left[f(x)\right]\right|\leq\epsilon\kern 5.0pt. We call r the seed length of G . We also say G \epsilon -fools \mathcal{F} over the Gaussian distribution. There has been a considerable amount of research developing PRGs for various Boolean function families, including halfspaces, polynomial threshold functions and intersections of halfspaces. Let \mathrm{sign}:\mathbb{R}\to\left\{0,1\right\} be the function such that \mathrm{sign}\!\left(x\right)=1 iff x\geq 0 . A halfspace is a Boolean function of the form f(x)=\mathrm{sign}\!\left(a_{1}x_{1}+\cdots+a_{n}x_{n}-b\right) for some a_{1},\cdots,a_{n},b\in\mathbb{R} . Halfspaces are a fundamental class of Boolean functions which have found significant applications in machine learning, complexity theory, theory of approximation and more. A very successful series of work produced PRGs that \epsilon -fools halfspaces with seed length poly-logarithmic in n and \epsilon^{-1} over both Boolean space [ Ser06 , DGJ+10 , MZ13 , GKM18 ] and Gaussian space [ KM15 ] . Polynomial threshold functions (PTFs) are functions of the form f(x)=\mathrm{sign}\!\left(p(x)\right) where p is a polynomial. We call f is a degree- d PTF if p is a degree- d polynomial. PTFs are natural generalization for halfspaces since a halfspace is a degree- 1 PTF. An explicit PRG that \epsilon -fools PTFs over Boolean space has been achieved with seed length (d/\epsilon)^{O(d)}\cdot\log n [ MZ13 ] . As for Gaussian space, a sequence of work [ DKN10 , Kan11a , Kan11b , Kan12 , MZ13 , Kan14 , Kan15 , OST20 , KM22 ] succeeds in giving a PRG with seed length polynomial in d , \epsilon^{-1} and \log n [ OST20 , KM22 ] . Another extension for halfspaces is intersections of k halfspaces which are polytopes with k facets. A line of work [ GOWZ10 , HKM13 , ST17 , CDS20 , OST22 ] results in PRGs with seed length polynomial in \log k , \log n and 1/\epsilon over Boolean space [ OST22 ] and over Gaussian space [ CDS20 ] . Considering the prosperity of PRGs for these functions families, we commence designing PRGs for functions of degree- d polynomial threshold functions . Definition 1.2 . We say a function F:\mathbb{R}^{n}\to\{0,1\} is a function of k degree- d PTFs if there exist k polynomials p_{1},\dots,p_{k}:\mathbb{R}^{n}\to\mathbb{R} of degree d and a Boolean function f:\{0,1\}^{k}\to\left\{0,1\right\} such that F(x)=f\!\left(\mathrm{sign}\!\left(p_{1}\!(x)\right),\dots,\mathrm{sign}\!\left(p_{k}\!(x)\right)\right)\kern 5.0pt. This family consumes all three function families we discussed above. For example, it includes intersections of halfspaces by setting d=1 and f(x)=x_{1}\cdots x_{k} . The research on PRGs for functions of PTFs is driven by several motivations beyond its fundamental role in derandomization tasks. For instance, the collection of satisfying assignments of an intersection of k degree- 2 PTFs corresponds to the feasible solutions set of an \{0,1\} -integer quadratic programing [ NW99 ] with k constraints. The investigation into the structure of these sets has been a central focus of extensive research in areas including learning theory, counting, optimization, and combinatorics. In this work, we consider building explicit PRGs for functions of degree- d PTFs over Gaussian space. Before presenting our main result, we briefly revisit relevant prior work on fooling functions of halfspaces. Table 1 : Related Work on PRGs for Intersections of PTFs Reference Function Family Seed length [ GOWZ10 ] Monotone functions of k halfspaces O((k\log(k/\epsilon)+\log n)\cdot\log(k/\epsilon)) [ HKM13 ] Intersections of k \delta -regular halfspaces O(\log n\log k/\epsilon) for \delta\leq\epsilon^{5}/(\log^{8.1}\!k\log(1/\epsilon)) [ ST17 ] Intersections of k weight- t halfspaces \mathrm{poly}\!\left(\log n,\log k,t,1/\epsilon\right) [ OST22 ] Intersections of k halfspaces \mathrm{polylog}\ m\cdot{\epsilon}^{-(2+\delta)}\cdot\log n for any absolute constant \delta\in(0,1) [ CDS20 ] Intersections of k halfspaces Arbitrary functions of k halfspaces O(\log n+\mathrm{poly}\!\left(\log k,1/\epsilon\right)) O(\log n+\mathrm{poly}\!\left(k,1/\epsilon\right)) [ DKN10 ] Intersections of k degree- 2 PTFs O(\log n\cdot\mathrm{poly}\!\left(k,1/\epsilon\right)) 1.1 Prior Work The related work is summarized in Table 1 . Gopalan, O’Donnell, Wu and Zuckerman [ GOWZ10 ] constructed PRGs for monotone functions of halfspaces . They modified the PRG for halfspaces in [ MZ13 ] and showed the modified PRG \epsilon -fools any monotone function of k halfspaces over a broad class of product distributions with seed length O((k\log(k/\epsilon)+\log n)\cdot\log(k/\epsilon)) . When k/\epsilon\leq\log^{c}n any c>0 , the seed length can be further improved to O(k\log(k/\epsilon)+\log n) . Harsha, Klivans and Meka [ HKM13 ] considered designing PRGs for intersections of regular halfspaces (i.e., halspaces with low influence). A halfspace f(x)=\mathrm{sign}\!\left(a_{1}x_{1}+\cdots+a_{n}x_{n}-b\right) is \delta -regular if \sum_{i}a_{i}^{4}\leq\delta^{2}\sum_{i}a_{i}^{2} . They gave an explicit PRG construction for intersections of k \delta -regular halfspaces over proper and hypercontractive distributions with seed length O(\log n\log k/\epsilon) when \delta is no more than a threshold. Their proof is based on developing an invariance principle for intersections of regular halfspaces via a generalization of the well-known Lindeberg method [ Lin22 ] and an anti-concentration result of polytopes in Gaussian space from [ KOS08 ] . By extending the approach of [ HKM13 ] and combing the results on bounded independence fooling CNF formulas [ Baz09 , Raz09 ] , Servedio and Tan [ ST17 ] designed an explicit PRG that \epsilon -fools intersections of k weight - t halfspaces over Boolean space with \mathrm{poly}\!\left(\log n,\log k,t,1/\epsilon\right) seed length. A halfspace f(x)=\mathrm{sign}\!\left(a_{1}x_{1}+\cdots+a_{n}x_{n}-b\right) is said to be weight- t if each a_{i} is an integer in [-t,t] . As for intersections of k general halfspaces, O’Donnell, Servedio and Tan [ OST22 ] gave a PRG construction over Boolean space with a polylogarithmic seed length dependence on k and n . Their proof involves a novel invariance principle for intersections of arbitrary halfspaces and a Littlewood–Offord

Read the complete text