We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>>

The permanent and mixed discriminant of positive matrices are classic problems for which we do not expect an efficient algorithm for exact computation. Thus much work has been done to understand how well we can bound and approximately compute these quantities. One line of research in this area begins with ... more >>>