Questions tagged [sampling]
The sampling tag has no usage guidance.
12
questions
10
votes
0
answers
375
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
6
votes
1
answer
174
views
Number of random bits necessary to approximate an arbitrary distribution
Given a discrete distribution $X$ and $\varepsilon\in(0,1)$, consider the minimal $m\in\mathbb{N}$ such that $\mathbf{SD}(f(U^m),X)\leq\varepsilon$, for some (the best, possibly inefficient) ...
- 179
6
votes
0
answers
136
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
146
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,153
3
votes
0
answers
141
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 \...
- 828
3
votes
0
answers
97
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.8k
2
votes
0
answers
41
views
definition of P-samplable distribution that allows non-binary fractions
Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
2
votes
0
answers
56
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
2
votes
0
answers
35
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 ...
- 627
0
votes
0
answers
53
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
0
votes
0
answers
112
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,041
-2
votes
1
answer
86
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