# Questions tagged [sampling]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
99 views

### Consistent Sampling a Random Walk

Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid. I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
• 898
101 views

### Complexity of sampling a clique uniformly at random

Let $G$ be an undirected graph, and let $C_1, ..., C_M$ denote all possible cliques in $G$. What is known on the complexity of sampling a clique uniformly at random. That is, returning clique $C_i$ ...
• 862
29 views

### Boltzmann sampling for knapsack constraints?

Is there an efficient algorithm to sample from the Boltzmann distribution defined by a knapsack constraint? More concretely, I have $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$. I ...
• 607
49 views

### Solving sampling problems with circuits?

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
326 views

### Finding uniformly random perfect matching of a graph

Problem: Suppose that we have a graph $G$ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...
• 121
92 views

### Boltzmann sampling for containers/dependent polynomials?

I’d like to randomly sample from dependently-typed data structures. Has anyone looked at extending Boltzmann sampling to containers or dependent polynomials?
• 32.1k
Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-...