Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
15
questions
6
votes
1answer
360 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 ...
1
vote
1answer
603 views
Derandomization of vertex cover algorithm
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.
Add to ...
3
votes
1answer
307 views
Find expectation with Chernoff bound
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
2
votes
1answer
2k views
How to get expected running time of hash table?
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
2answers
380 views
Choosing error rates for probabilistic algorithms
Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
5
votes
1answer
3k 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 ...
9
votes
3answers
3k 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 ...
8
votes
1answer
700 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 ...
3
votes
2answers
2k 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:
...
2
votes
1answer
141 views
Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?
Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine ...
5
votes
1answer
516 views
What is an example of a weakly universal hash function that is not pairwise independent?
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$
Here the function $h:U \rightarrow [m]$ is chosen uniformly from the ...
4
votes
3answers
419 views
Why do Bloom filters work?
Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a ...
3
votes
3answers
3k views
What would be a decent threshold for classification problem?
I'm using machine-learning algorithms to solve binary classification problem (i.e. classification can be 'good' or 'bad'). I'm using SVM based algorithms, ...
1
vote
1answer
128 views
Can BPP be bounded around any constant other than 1/2?
A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
-1
votes
1answer
126 views
Prove that we can change probability in definition of PP class
According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer ...
