Questions tagged [sampling]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
1 answer
168 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) ...
Nathan's user avatar
  • 179
2 votes
0 answers
37 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 ...
Shivaram Lingamneni's user avatar
-2 votes
1 answer
70 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 ...
Ayoubayjx's user avatar
  • 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 ...
user2316602's user avatar
3 votes
0 answers
131 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 \...
delete000's user avatar
  • 818
6 votes
0 answers
135 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 ...
Thomas Ahle's user avatar
3 votes
1 answer
140 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$ ...
user3508551's user avatar
  • 1,153
2 votes
0 answers
34 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 ...
Asterix's user avatar
  • 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 ...
trillianhaze's user avatar
10 votes
0 answers
363 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 ...
Alt-Tab's user avatar
  • 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?
Neel Krishnaswami's user avatar
0 votes
0 answers
108 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-...
Mahdi Cheraghchi's user avatar