Efficient inference of interventional distributions

We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let P be a causal model on a set V of observable variables on a given causal graph G. For sets X,Ysubseteq V, and setting bf x to X, let Pbf x(Y) denote the interventional distribution on Y with respect to an intervention bf x to variables bf x. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), gave an exact characterization of the class of causal graphs for which the interventional distribution Pbf x(Y) can be uniquely determined. We give the first efficient version of the Shpitser-Pearl algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph G on observable variables V, a setting bf x of a set X subseteq V of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution hatP that is varepsilon-close (in total variation distance) to Pbf x(Y) where Y=Vsetminus X, if Pbf x(Y) is identifiable. We also show that when Y is an arbitrary set, there is no efficient algorithm that outputs an evaluator of a distribution that is varepsilon-close to Pbf x(Y) unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.