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

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$ polynomial threshold functions (PTFs) over Gaussian space. Our main result is an explicit construction of PRG with seed length $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(k,d,1\mathrm{/}\epsilon )\cdot \log n$ that can fool any function of $k$ degree-$d$ PTFs with probability at least $1-\epsilon$. More specifically, we show that the summation of $L$ independent $R$-moment-matching Gaussian vectors $\epsilon$-fools functions of $k$ degree-$d$ PTFs, where $L=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(k,d,\frac{1}{\epsilon })$ and $R=O(\log \frac{kd}{\epsilon })$. The PRG is then obtained by applying an appropriate discretization to Gaussian vectors with bounded independence.