# Questions tagged [probabilistic-algorithms]

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

211 questions
Filter by
Sorted by
Tagged with
7k views

### Deleting in Bloom Filters

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
• 259
476 views

### Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an $NP$-...
• 29.7k
408 views

### Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
• 3,657
2k views

### Probabilistic methods for undecidable problem

An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
• 219
728 views

### Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
• 747
775 views

### Probability Distributions and Computational Complexity

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem ...
• 8,298
158 views

### Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
• 580
870 views

### Prove or refute: BPP(0.90,0.95) = BPP

I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time ...
• 462
7k views

### What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
• 1,135
703 views

### Are probabilistic search data structures useful?

A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these ...
• 235
2k views

### An edge that connects more than two nodes in a graph?

Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
329 views

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

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results match, start over,...
• 9,521
3k 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 ...
• 243
4k views

### What is With High Probability on Probabilistic Algorithms?

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn'...
4k views

### Computer science problems related to music?

Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
• 1,006
1k views

### Bloom filter and perfect hashing

A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple ...
• 325
493 views

### Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
• 211
540 views

• 141
200 views

### About sorting numbers in linear time

If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time? It seems to me that some such method exists which uses binary ...
• 97
406 views

• 141
3k views

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

Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language: ...
• 155
847 views

### Prove that PP is closed under complement

I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain: By the definition of PP there is a polynomial-time probabilistic algorithm ...
• 311
313 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 ...
• 143
160 views

2k views

### Bloom Filter for 208 million URLs

I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it ...
• 157