12
There is a simple algorithm for V3.
I'll use the convention that there are $(2n)^3$ possible clauses,
so $2^{8n^3}$ formulas.
(This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.)
Pick a random assignment from $\{0,1\}^n$.
For each of the $7n^3$ possible clauses that are true ...
11
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 model (Section 3.1). Then, they further illustrate how to map their spin system model to the problem of uniformly sampling from the order ideals of a poset which, ...
9
The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that ...
9
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 probability $|A| / |B|$, which is indeed close to enumerating the elements of $A$, and thus computing its size.
8
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 use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state ...
7
Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)
Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x ...
6
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, taking an $\epsilon$-net sample of a set of points in the plane, computing its smallest enclosing disk, results in a disk $D$ that contains $(1-\epsilon)$ fraction ...
6
No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).
5
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 distributions $\mathcal{D}_0$, $\mathcal{D}_1$, where these two distributions are "close". Suppose we have $n$ observations (i.e., a sequence of $n$ numbers ...
4
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.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - ...
4
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 probability $1/2$ on each iteration, while for vertices on the path, the probability is $1/2+1/2k$, where $k$ is the number of vertices on the path.
Thus, if $s\approx ...
3
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 case of e.g. sum or sum of squared distances to a shape or set of shapes (as PCA, linear regression or k-means) there is a generic reduction from eps-net to ...
3
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 uniform convergence can be bounded using entropy.
As Aryeh observes, it suffices to bound $\mathbb{E}[\|\overline X - \mu\|_\infty]$.
First, use the duality ...
3
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 remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$.
Using Jensen's inequality,
$$ (\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\...
3
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 algorithm whose clusters are not limited in radius.
The problem is known to be NP-complete for $k\geq 2$.
For unit balls, this problem has a PTAS ( ($1+\epsilon$)-...
3
One line of attack on approximate quantiles is via streaming algorithms. In one scan of the data (i.e., very efficiently) you can get estimates for the quantiles within error $\epsilon N$ for any $\epsilon > 0$, which means that if your true marker is (say) $5\%$, and $\epsilon = 0.01$, your true marker will be between $4-6\%$. There's a nice survey of ...
3
It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see http://en.wikipedia.org/wiki/Selection_algorithm).
2
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 that, per conjecture, it doesn't affect it. People conjecture that BPP = P, i.e., that randomized algorithms can be derandomized with pseudo-random-number ...
2
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 approximately normal distribution, with mean $0$ and covariance matrix given by the inverse Fisher matrix, see Section 9 here:
http://www.stat.cmu.edu/~larry/=stat705/...
1
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$ samples (after transforming to Z).
It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent ...
1
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 chooses $k$ completely random elements $v_1,\ldots,v_k$ of $F_2^n$ and outputs their span $V$.
A little extra work is needed to bound the probability that the $k$ ...
1
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 multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed?
Only top voted, non community-wiki answers of a minimum length are eligible
