Bounded Independence Fools Degree-2 Threshold Functions

Details Bounded Independence Fools Degree-2 Threshold Functions Bounded Independence Fools Degree-2 Threshold Functions

2009-11-17

arxiv.org/abs/0911.3389v2

Computer Science

Computational Complexity

Using v1 numbering: removed Lemma G.5 from the Appendix (it was wrong). Net effect is that Theorem G.6 reduces the m^6 depende

Scientific paper

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 epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of k-wise independent distributions, we obtain a broad class of explicit generators that epsilon-fool the class of degree-2 threshold functions with seed length log(n)*poly(1/epsilon). Our approach is quite robust: it easily extends to yield that the intersection of any constant number of degree-2 threshold functions is epsilon-fooled by poly(1/epsilon)-wise independence. Our results also hold if the entries of x are k-wise independent standard normals, implying for example that bounded independence derandomizes the Goemans-Williamson hyperplane rounding scheme. To achieve our results, we introduce a technique we dub multivariate FT-mollification, a generalization of the univariate form introduced by Kane et al. (SODA 2010) in the context of streaming algorithms. Along the way we prove a generalized hypercontractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. These techniques may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Bounded Independence Fools Degree-2 Threshold Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounded Independence Fools Degree-2 Threshold Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded Independence Fools Degree-2 Threshold Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-239880