Questions tagged [probabilistic-algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
Igglyboo's user avatar
  • 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$ ...
David Richerby's user avatar
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 ...
Alex's user avatar
  • 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 ...
omega's user avatar
  • 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 ...
bruce_springsteen's user avatar
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 ...
Zix's user avatar
  • 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 ...
Numerator's user avatar
  • 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 ...
user6818's user avatar
  • 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 ...
Simd's user avatar
  • 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 ...
user220201's user avatar
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: ...
woz's user avatar
  • 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, ...
Ziv Levy's user avatar
  • 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 ...
johnson's user avatar
  • 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. ...
e_noether's user avatar
  • 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 ...
biddlesby's user avatar
  • 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 ...
John e's user avatar
  • 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 ...
Alex's user avatar
  • 11