Fooling functions of halfspaces under product distributions

Details Fooling functions of halfspaces under product distributions Fooling functions of halfspaces under product distributions

2010-01-11

arxiv.org/abs/1001.1593v1

Computer Science

Computational Complexity

Scientific paper

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0. Our first main result shows that a recent pseudorandom generator construction of Meka and Zuckerman [MZ09], when suitably modifed, can fool arbitrary functions of d halfspaces under product distributions where each coordinate has bounded fourth moment. To eps-fool any size-s, depth-d decision tree of halfspaces, our pseudorandom generator uses seed length O((d log(ds/eps)+log n) log(ds/eps)). For monotone functions of d halfspaces, the seed length can be improved to O((d log(d/eps)+log n) log(d/eps)). We get better bounds for larger eps; for example, to 1/polylog(n)-fool all monotone functions of (log n)= log log n halfspaces, our generator requires a seed of length just O(log n). Our second main result generalizes the work of Diakonikolas et al. [DGJ+09] to show that bounded independence suffices to fool functions of halfspaces under product distributions. Assuming each coordinate satisfies a certain stronger moment condition, we show that any function computable by a size-s, depth-d decision tree of halfspaces is eps-fooled by O(d^4s^2/eps^2)-wise independence.

Affiliated with

Also associated with

No associations

Rating

Fooling functions of halfspaces under product distributions 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 Fooling functions of halfspaces under product distributions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fooling functions of halfspaces under product distributions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718958