# Tag Info

### Probabilistic methods for undecidable problem

So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we ...
• 3,183
Accepted

### Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$...
• 162k
Accepted

### Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime. Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
• 121

• 278k
Accepted

• 278k
Accepted

### $k$-coloring in BPP, implies $k$-coloring in ZPP

This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$? Since $k$-coloring is NP-complete, what you are asked to show is: ...
• 7,118
Accepted

### What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the ...
• 22.6k

### Why is tabulated hashing 3-wise independent but not 4-wise independent?

For any $h = h_{A,B}$ and $x,x',y,y' \in \{0,1\}^w$, $$h(x,y) \oplus h(x',y) \oplus h(x,y') \oplus h(x',y') = 0.$$
• 278k
Accepted

### Question about "with high probability"

Yes. The common convension of "with high probability" (that I know of) states that for every $0\le \delta<1$, there is some $n_0$ such that for $n>n_0$ it holds that the probability \$P(...
• 11.6k