Sampling Boolean Functions over Abelian Groups and Applications

Abstract.

We obtain efficient sampling methods for recovering or compressing functions over finite Abelian groups with few Fourier coefficients, i.e., functions that are (approximable by) linear combinations of few, possibly unknown Fourier basis functions or characters. Furthermore, our emphasis is on efficiently and deterministically finding small, uniform sample sets, which can be used for sampling all functions in natural approximation classes of Boolean functions. Due to this requirement, even the simplest versions of this problem (say, when the set of approximating characters is known) require somewhat different techniques from the character theory of finite Abelian groups 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 strings, and testing linearity; we also state highly related open problems that are not only applicable in these contexts, but are also of independent mathematical interest.