<p>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.</p>

CC BY-SA 2.5
2010-08-26T18:46:27.780Z
Yes, I guess that polynomial-time samplable is the term I am looking for.  It came up in the discussion here http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5326
Jeff
CC BY-SA 2.5
2010-09-29T23:56:55.390Z
Could you please tell if this answered you question or you want a definition of "polynomial-time samplable distribution"?
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-08-26T04:52:40.033Z
2010-08-26T04:52:40.033Z
Grigory Yaroslavtsev
<p>What does it mean for a distribution to be efficiently samplable?</p>

<p>This came up in the discussions about the distributions used in the recent attempted P!=NP proof.</p>

<p>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.</p>

<p>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? </p>

<p>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.</p>

<sample-complexity>
Efficiently Samplable Distributions
Jeff
# Efficiently Samplable Distributions

(Asked by: username_0 on 2010-08-26)

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.

**Tags:** sample-complexity

---

## 1 answers

### Answer by username_1 on 2010-08-26. Score: 2

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.

> **Comments:**
> **username_0**: Yes, I guess that polynomial-time samplable is the term I am looking for.  It came up in the discussion here http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5326  
> **username_1**: Could you please tell if this answered you question or you want a definition of "polynomial-time samplable distribution"?  

---

