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,075
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
  • 159k
10 votes
Accepted

Why is ZPP = RP ∩ co-RP?

The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though. Markov's inequality ...
Sarvottamananda's user avatar
7 votes

What does the "principle of deferred decisions" formally mean

The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent. One way is that you can toss a coin yourself at the exact step when you ...
Banach Tarski's user avatar
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

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
  • 111
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 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

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

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,852
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

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
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

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

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
  • 159k
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

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
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,951
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
Accepted

Ways to perform "batch" Approximate Member Queries efficiently

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.) This might be slow, however, ...
jbapple's user avatar
  • 3,380
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

A clarification on $PP$

First, let me change your definition of PP a little bit: On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$ On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$...
mdxn's user avatar
  • 1,301
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

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

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