Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
17
questions
7
votes
1
answer
459
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
3
votes
2
answers
521
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$ ...
- 81.4k
3
votes
1
answer
369
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 ...
- 31
2
votes
1
answer
3k
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 ...
- 553
1
vote
1
answer
683
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 ...
14
votes
4
answers
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
9
votes
1
answer
857
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 ...
- 452
7
votes
1
answer
6k
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,115
5
votes
1
answer
742
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 ...
- 880
4
votes
4
answers
514
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 ...
- 143
4
votes
2
answers
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
3
votes
3
answers
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, ...
- 133
2
votes
1
answer
172
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 ...
- 151
1
vote
1
answer
390
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,269
1
vote
1
answer
34
views
Predicting the outcome of sporting events with multiplicative scoring
In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes ...
- 123
1
vote
1
answer
208
views
Uniform sampling with constraints
Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the ...
- 13
0
votes
1
answer
227
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 ...
- 11