Questions tagged [sampling]
The sampling tag has no usage guidance.
4
questions
0
votes
0
answers
47
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 ...
- 21
10
votes
0
answers
295
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 ...
- 101
3
votes
0
answers
89
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?
- 31.6k
0
votes
0
answers
91
views
Efficient sampling of primes
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-...
- 4,011