Skip to main content
19 votes

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 ...
Arno's user avatar
  • 3,183
12 votes
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$...
D.W.'s user avatar
  • 162k
7 votes
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 ...
Rajat De's user avatar
  • 121
6 votes

Why does Karger's algorithm work "with high probability"

Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2})$, i.e. with probability $\ge \frac{c}{n^...
Ariel's user avatar
  • 13.4k
6 votes
Accepted

Is there a complexity class QPP?

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
Yuval Filmus's user avatar
5 votes
Accepted

What is an example of a weakly universal hash function that is not pairwise independent?

Let $U = [m]$, and let $h$ be the identity function. If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{...
Yuval Filmus's user avatar
5 votes
Accepted

Is there a concept of probabilistic quantum computers?

It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in ...
Adam Zalcman's user avatar
4 votes
Accepted

Analysis of a randomized algorithm for independent set construction

You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then \begin{align} \...
PSPACEhard's user avatar
4 votes

Why does Karger's algorithm work "with high probability"

Approximately, if a chance NOT to find a cut in independent contraction is $1-\frac{a}{n^2}$, then a chance to find it in $n^2\log n$ contractions is $$ 1-\left(1-\frac{a}{n^2}\right)^{n^2\log n}=1-\...
user3605620's user avatar
4 votes

How can we get a Las Vegas algorithm from a Monte Carlo one?

First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is ...
YOUSEFY's user avatar
  • 289
4 votes
Accepted

Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

It is defined to be a probability. A probability is by definition already normalized. In particular, we are guaranteed that $$\sum_{j=1}^N \gamma_j(1) = 1,$$ as there are only $N$ possibilities ...
D.W.'s user avatar
  • 162k
4 votes

Doesn't a quantum algorithm being deterministic contradict the superposition principle?

If the algorithm has no error, then the system is not in a superposition when it is measured, but it is possible it was in a superposition during the computation, after which it was cleverly ...
Lieuwe Vinkhuijzen's user avatar
4 votes
Accepted

Are there any useful deterministic quantum algorithms for decision problems?

There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions": a total boolean ...
Craig Gidney's user avatar
  • 5,862
4 votes
Accepted

Determine number of values less than mean in one pass through list

Consider an algorithm for arrays of length $n$ consisting of entries from $0$ to $n$, and using space $S$ bits. Suppose that the first half of the array consists of pairs $a,n-a$ (where $a \leq n/2$)....
Yuval Filmus's user avatar
4 votes

Find expectation with Chernoff bound

In this answer I assume given scores are pairwise didtinct. Note that the probability of two scores being equal is 0 since we have continuous probability. I think the same proof can be tweaked to span ...
Narek Bojikian's user avatar
3 votes
Accepted

Algorithm for finding cliques

Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/...
Yuval Filmus's user avatar
3 votes
Accepted

proving $IP^\star = NP$

If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(...
Yuval Filmus's user avatar
3 votes
Accepted

What does it mean for a problem to be solved in polynomial time "relative to" an oracle?

Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In ...
Yuval Filmus's user avatar
3 votes

Deleting in Bloom Filters

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when ...
Kent Munthe Caspersen's user avatar
3 votes

3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

Consider the greedy algorithm that loops through the vertices in arbitrary order and assigns each vertex $v$ the least popular color among its previously-colored neighbors. Each vertex $v$ gets a ...
JeffE's user avatar
  • 8,713
3 votes
Accepted

Prove that PP is closed under complement

$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that ...
adrianN's user avatar
  • 5,961
3 votes
Accepted

Average Case Analysis for finding max and min value on an array

First, note that the first comparison will always compare $n-1$ times, independent of the distribution of the input. So, what you really want to know is how many times the second part of the if ...
LionsWrath's user avatar
3 votes
Accepted

Small space hash functions that are weakly but not strongly universal

Let $H$ be a family of strongly universal hash functions from $U$ to $[m]$. Construct a new family of hash functions from $U \cup \{x\} \to [m]$ by extending all functions $h \in H$ with $h(x) = 1$. ...
Yuval Filmus's user avatar
3 votes

Derandomization of vertex cover algorithm

First, let us repeat the analysis of the algorithm. Fix some optimal vertex cover OPT, with cost $O$. Let $S$ be the cost of the vertex cover produced by the algorithm. Let $A_e$ be the indicator ...
Yuval Filmus's user avatar
3 votes
Accepted

Probability of terminating in a state in a probabilistic algorithm

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)...
Yuval Filmus's user avatar
3 votes
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: ...
Caleb Stanford's user avatar
3 votes
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 ...
Juho's user avatar
  • 22.6k
3 votes

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. $$
Yuval Filmus's user avatar
3 votes
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(...
nir shahar's user avatar
  • 11.6k
2 votes

Clock solitaire game and principle of deferred decision

You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the ...
Yuval Filmus's user avatar

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