What does it mean for a distribution to be efficiently samplable?This came up in the discussions about the distributions used in the recent attempted P!=NP proof.The context was that a distribution modeled as a directed graphical model that can be factored such that each factor is sub-exponential in size or dependent on a polylog number of parents then it is efficiently samplable.  In contrast, if a factor is dependent on O(n) parents then the table size is exponential and no longer efficiently samplable.The barrier here to efficient sampling appears to be the exponential size of the table required to describe the factor that depends on O(n) parents.  Is this the key point or is there some other barrier? I should clarify, that if one could replace the exponential sized table for the conditional distribution that depends on O(n) parents with a polynomial time function that returns the value of $P(x_n;x_1...x_{n-1})$ given the parents then it seems the problem becomes efficiently samplable.
Efficiently Samplable Distributions
sample complexity