Questions tagged [sampling]
The sampling tag has no usage guidance.
10
questions
-2
votes
1
answer
58
views
What is really the difference between membership queries and "querying in i.i.d?
I'm struggling at finding the difference between algorithms that use i.i.d random queries then request their labels and algorithms that use membership queries.
Membership queries allow the learner to ...
- 122
2
votes
0
answers
53
views
Approximately sampling from a discrete unimodal distribution with large support
I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known.
I ...
- 630
3
votes
0
answers
122
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 778
6
votes
0
answers
133
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 ...
- 958
3
votes
1
answer
123
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$ ...
- 1,078
2
votes
0
answers
32
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 ...
- 617
0
votes
0
answers
52
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 ...
- 121
10
votes
0
answers
353
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
3
votes
0
answers
95
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.4k
0
votes
0
answers
105
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