# Tagged Questions

Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.

40 views

### Clock solitaire game and principle of deferred decision

I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. ...
31 views

### Proving that $BPP^{BPP}=BPP$

I'm trying to prove that $BPP^{BPP}=BPP$. $BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$.. Can anyone help?
93 views

### Are there any useful deterministic quantum algorithms for decision problems?

The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (...
340 views

I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link). It states that a single round of contractions yields a min-cut with probability $\... 1answer 30 views ### Replacing n with 2n in asymptotic bounds I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem$6$of the paper on page 632, the authors go on ... 1answer 54 views ### Why is ZPP = RP ∩ co-RP? I am trying to prove the theorem that ZPP = RP$\; \cap \; co-RP$. If$L \in \; \subseteq RP \; \cap \; co-RP$then I can see that it belongs to$ZPP$. But I am unable to prove the reverse direction, ... 1answer 53 views ### A clarification on$PP$Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following: On a YES instance, output YES with probability$1/2 + 1/2^n$, where n is ... 0answers 52 views ### How can we get a Las Vegas algorithm from a Monte Carlo one? I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills. Here is the exercise: Exercise 1.3: ... 1answer 78 views ### What does the “principle of deferred decisions” formally mean I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ... 1answer 62 views ### Probability bounds on size of smaller partition in randomized quicksort Let$0 < a < 0.5$be some constant. We have an$n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability$1-...
40 views

I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I ...
40 views

### Logarithmic Randomness is Necessary for PCP Theorem

I am trying to proof the following statement: If ${\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $r(n)=o(\log n)$, then ${\sf P}={\sf NP}$. Here are my ideas for the proof: It can be easily worked ...
657 views

### What is the best you can do with a noisy message?

You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2. ...
43 views

### Ways to perform “batch” Approximate Member Queries efficiently

In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number ...
117 views

### probablistic procedure to permutate array

input : $array[1...n]$ output: permutated array Our algorithm should be probablistic and complexity should be $O(n)$. Could you give me hint ? My weakness is probability theory and it is why I have ...
126 views

### Probabilistic algorithm with two-sided error

I am currently studying probabilistic algorithms and came across three major complexity classes: BPP: worst-case polynomial time, two-sided error RP: worst-case polynomial time, one-sided error ZPP: ...