Supplementary Material for A polynomial time algorithm for learning

This same algorithm can then be used to reconstruct the true DAGGfrom the true ordering . Once the ordering is known, existing nonlinear variable selection methods [4, 11, 16, 25, 28, 46] suffice to learn the parent setspa(j)and hence the graphG. In our experiments, we use exactly this procedure to learnGfrom the order, based on the data. There are two cases: (i)Bj =, and (ii)Bj 6= . If instead we haveσ23 = var(z3) = 1/3, the condition would be violated.