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.


1 Answer 1


Could you please provide a reference to the context, where the term "efficiently samplable distribution" is used? Because there is a well-known concept called "polynomial-time samplable distribution", so because in TCS we usually mean "efficient" = "polynomial-time", I guess these two can coincide.

  • $\begingroup$ Yes, I guess that polynomial-time samplable is the term I am looking for. It came up in the discussion here rjlipton.wordpress.com/2010/08/12/… $\endgroup$
    – Jeff
    Aug 26, 2010 at 18:46
  • $\begingroup$ Could you please tell if this answered you question or you want a definition of "polynomial-time samplable distribution"? $\endgroup$ Sep 29, 2010 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.