  We give improved pseudorandom generators (PRGs) for Lipschitz functions of
low-degree polynomials over the hypercube. These are functions of the form
psi(P(x)), where P is a low-degree polynomial and psi is a function with small
Lipschitz constant. PRGs for smooth functions of low-degree polynomials have
received a lot of attention recently and play an important role in constructing
PRGs for the natural class of polynomial threshold functions. In spite of the
recent progress, no nontrivial PRGs were known for fooling Lipschitz functions
of degree O(log n) polynomials even for constant error rate. In this work, we
give the first such generator obtaining a seed-length of (log
n)\tilde{O}(d^2/eps^2) for fooling degree d polynomials with error eps.
Previous generators had an exponential dependence on the degree.
  We use our PRG to get better integrality gap instances for sparsest cut, a
fundamental problem in graph theory with many applications in graph
optimization. We give an instance of uniform sparsest cut for which a powerful
semi-definite relaxation (SDP) first introduced by Goemans and Linial and
studied in the seminal work of Arora, Rao and Vazirani has an integrality gap
of exp(\Omega((log log n)^{1/2})). Understanding the performance of the
Goemans-Linial SDP for uniform sparsest cut is an important open problem in
approximation algorithms and metric embeddings and our work gives a
near-exponential improvement over previous lower bounds which achieved a gap of
\Omega(log log n).
