A PRG for lipschitz functions of polynomials with applications to sparsest cut
A PRG for lipschitz functions of polynomials with applications to sparsest cut
We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form ψ(P(x)), where P:{1,-1}n -> R is a low-degree polynomial and ψ:R -> R is a function with small Lipschitz constant. PRGs for smooth functions of low-degree polynomials have received …