The following problem has long been studied in the TCS literature: learn
a probability distribution on n bits which is known to be a mixture of k
distributions, in each of which the bits are independent. This (as a
parameter-identification problem) is intermediate in expressiveness
between the much simpler case of iid bits, and the much more ambitious
case in which the bits are not independent at all, but are related
through a Causal Bayesian Network. I’ll give an overview of a series of
works showing how to
(a) Reduce the network case to the independent case (by a conditioning
method),
(b) Reduce the independent case to the iid case (by an algorithm which
creates “synthetic bits”), and finally,
(c) Give upper and lower bounds for the iid case (the algorithm here is
the two-century-old method of Prony).

Based on joint works with Chaitanya Swamy (Waterloo), Yuval Rabani
(Hebrew U), Jian Li (Tsinghua), Spencer Gordon (Caltech) and Bijan
Mazaheri (Caltech)