Sampling Boolean functions over Abelian groups and applications

We obtain efficient sampling methods for recovering or compressing function s over finite Abelian groups with few Fourier coefficients, i.e., functions that are (approximable by) linear combinations of few, possibly unknown Fo urier basis functions or characters. Furthermore, our emphasis is on effici ently and deterministically finding small, uniform sample sets, which can b e used for sampling all functions in natural approximation classes of Boole an functions. Due to this requirement, even the simplest versions of this p roblem (say, when the set of approximating characters is known) require som ewhat different techniques from the character theory of finite Abelian grou ps that are commonly used in other discrete Fourier transform applications. We briefly discuss applications of our efficient, uniform sampling methods in computational learning theory, efficient generation of pseudorandom str ings, and testing linearity; we also state highly related open problems tha t are not only applicable in these contexts, but are also of independent ma thematical interest.