Bounded
Ilias Diakonikolas, Daniel Kane, Jelani Nelson
51st Annual Symposium on Foundations of Computer Science (FOCS), 2010
Abstract:
Let x be a random vector coming from any k-wise
independent distribution over {-1, 1}n
. For an n-variate degree-2
polynomial p, we prove that E[sgn(p(x))]
is determined up to an additive ε for k = poly(1/ε).
This gives a large class of explicit pseudorandom generators against such
functions and answers an open question of Diakonikolas
et al. (
In the process, we develop a novel analytic technique we dub
multivariate FT-mollification. This
provides a generic tool to approximate bounded (multivariate) functions by low-degree polynomials (with respect to
several different notions of approximation). A univariate
version of the method was introduced by Kane et al. (SODA 2010) in the context
of streaming algorithms. In this work, we refine it and generalize it to the
multivariate setting. We believe that our technique is of independent
mathematical interest. To illustrate its generality, we note that it implies a
multidimensional generalization of
To obtain our main result, we combine the FT-mollification technique with several linear algebraic and probabilistic tools. These include the invariance principle of Mossell, O'Donnell and Oleszkiewicz, anti-concentration bounds for low-degree polynomials, an appropriate decomposition of degree-2 polynomials, and a generalized hyper-contractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. Our analysis is quite modular; it readily adapts to show that intersections of halfspaces and degree-2 threshold functions are fooled by bounded independence. From this it follows that Ω(1/ ε2)-wise independence derandomizes the Goemans-Williamson hyperplane rounding scheme.
Our techniques unify, simplify, and in some cases improve several recent results in the literature concerning threshold functions. For the case of “regular” halfspaces we give a simple proof of an optimal independence bound of Θ(1/ ε2), improving upon Diakonikolas et al. (FOCS 2009) by polylogarithmic factors. This yields the first optimal derandomization of the Berry-Esséen theorem and ̶ combined with the results of Kalai et al. (FOCS 2005) ̶ implies a faster algorithm for the problem of agnostically learning halfspaces.
Preliminary version: [PDF]
Arxiv report: [arXiv]