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

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$ polynomial threshold functions (PTFs) over Gaussian space. Our main result is an explicit construction of PRG with seed length $\mathrm{poly}(k,d,1/\hat{I}\mu )\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 $\hat{I}\mu$-fools functions of $k$ degree-$d$ PTFs, where $L=\mathrm{poly}(k,d,\frac{1}{\hat{I}}\mu )$ and $R=O(\log \frac{kd}{\hat{I}}\mu )$. The PRG is then obtained by applying an appropriate discretization to Gaussian vectors with bounded independence.

update citations