We present a polynomial time algorithm for learning a mixture of any
constant number of unknown product distributions over {0,1}^n. Previous
polynomial time algorithms were only able to learn mixtures of two product
distributions.

Via a reduction from a notorious hard problem in computational learning
theory, we also give evidence that no polynomial time algorithm can learn
mixtures of a superconstant number of product distributions over {0,1}^n.
This reduction suggests that our results may be essentially the best which
can be achieved by any polynomial time algorithm for this problem.

In fact, our technique is quite general and can efficiently learn many
classes of mixtures of O(1) product distributions over R^n, including
mixtures of axis-aligned Gaussians and mixtures of product distributions
over sets of finite size.

This is joint work with Jon Feldman and Rocco Servedio of Columbia
University.