11 votes
Accepted

Sampling monotone Boolean functions

In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system ...
user avatar
  • 3,381
9 votes
Accepted

Almost uniform sampling implies approximate counting

Given a set $A \subseteq B$, if you can sample uniformly from $B$, then you can estimate by repeated sampling the probability of the event that the sample is in $A$. That is, you can approximate the ...
user avatar
8 votes
Accepted

Qubit gates in google supremacy

Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
user avatar
6 votes

Coreset and VC dimension

Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, ...
user avatar
5 votes

Sample complexity of distinguishing two Gaussian distributions?

I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature. Suppose we want to distinguish between two ...
user avatar
  • 10.5k
4 votes
Accepted

Determining the number of clusters using property testing algorithm

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp....
user avatar
4 votes
Accepted

How many samples are needed to reconstruct a path?

Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit. For vertices outside the path, they agree with ...
user avatar
3 votes

Is uniform convergence faster for low-entropy distributions?

This is very much a partial answer to my question. I'm hoping for a much better bound (or a counterexample). I managed to show a very weak bound. It is not very useful, but it does at least show that ...
user avatar
  • 2,743
3 votes

Is uniform convergence faster for low-entropy distributions?

First, let's use McDiarmid's inequality to conclude that $$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge \mathbb{E}|| \bar X - \mu ||_\infty + \varepsilon \right] \le e^{-2n\varepsilon^2},$$ so it ...
user avatar
  • 10.1k
3 votes
Accepted

Coreset and VC dimension

The answer of Har-Peled is mainly regarding problems where you wish to cover points by shapes (e.g. balls). A strong relation to eps-nets and hitting sets can be found e.g. in his paper here For the ...
user avatar
3 votes
Accepted

Approximating the value of k in $k$-mean clustering problem

This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering ...
user avatar
  • 9,378
2 votes

What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?

The gist of the question is, given that quantum probability is a source of true randomness, how does that effect the extended (or efficient, or polynomial-time) Church-Turing thesis? The answer is ...
2 votes
Accepted

Sample complexity for learning Boltzmann Distribution parameters

Under appropriate smoothness conditions (satisfied by the Boltzmann distribution), the maximum likelihood is asymptotically normal. Meaning: the vector $\sqrt n(\theta-\hat\theta)$ will have ...
user avatar
  • 10.1k
2 votes
Accepted

Lower bound for the OR problem

After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I ...
user avatar
1 vote
Accepted

Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

From the DKW inequality, it follows one can learn an arbitrary distribution over $\mathbb{R}$ (and in particular over $\{1,2,\dots,n\}$ to Kolmogorov distance* $\varepsilon$ with probability at least $...
user avatar
  • 4,341
1 vote
Accepted

How well do subspaces hit sets

Here's an $\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$ lower bound following the discussion here with Yuval, and another one with Ross Berkowitz. I assume for simplicity that the sampling process ...
user avatar
  • 217
1 vote

Sample Complexity for Order Statistics

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ ...
user avatar
1 vote

Evaluating the expected value of negatively correlated random variables

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible