Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
203
questions
14
votes
4
answers
6k
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
11
votes
1
answer
445
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.5k
11
votes
0
answers
396
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,627
10
votes
4
answers
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
10
votes
2
answers
703
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 ...
- 737
10
votes
1
answer
661
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,268
10
votes
0
answers
156
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 ...
- 560
9
votes
1
answer
847
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
9
votes
2
answers
700
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 ...
- 225
8
votes
2
answers
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 ...
- 293
8
votes
1
answer
317
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,431
8
votes
1
answer
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
8
votes
1
answer
3k
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'...
- 81
7
votes
3
answers
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 ...
7
votes
2
answers
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
7
votes
1
answer
5k
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,105
7
votes
1
answer
453
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
7
votes
1
answer
537
views
Probabilistic test of matrix multiplication with one-sided error
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\...
- 489
6
votes
1
answer
6k
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, ...
- 2,923
6
votes
1
answer
248
views
Probabilistic poly-time machine always halts on all inputs?
In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.
Is the intention really to say that the machine halts for all inputs, ...
user583311
6
votes
1
answer
380
views
BPP search: what does boosting correctness entail?
It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how ...
- 245
6
votes
1
answer
121
views
Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing through a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain whose ...
- 3,760
5
votes
2
answers
7k
views
why not just use a random number generator as a hash function?
I guess at the heart of this is that I don't really understand hash functions.
One article says any function mapping objects to an object of fixed size:
A hash function usually means a function ...
- 1,911
5
votes
1
answer
483
views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
- 265
5
votes
1
answer
733
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 ...
- 860
5
votes
1
answer
771
views
Analysis of a randomized algorithm for independent set construction
Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.
Step $1$: Delete each vertex (...
- 309
5
votes
1
answer
139
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 ...
- 177
5
votes
1
answer
535
views
Can a probabilistic Turing Machine compute an uncomputable number?
Can a probabilistic Turing Machine compute an uncomputable number?
My question probably does not make sense, but, that being the case, is
there a reasonably simple formal explanation for it. I should ...
- 19.3k
5
votes
1
answer
658
views
Understanding the Sipser-Gacs-Lautemann theorem
The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input.
The class $\Sigma^p_2$ contains all ...
- 1,198
4
votes
4
answers
511
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
513
views
Why does Karger's algorithm work "with high probability"
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 $\...
- 141
4
votes
2
answers
140
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
4
votes
1
answer
395
views
What is known about coRL and RL?
Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.
Are they the same class?
What are $\...
- 143
4
votes
2
answers
465
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 (...
- 984
4
votes
2
answers
402
views
Why is tabulated hashing 3-wise independent but not 4-wise independent?
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
- 141
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
4
votes
1
answer
758
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
4
votes
1
answer
312
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
4
votes
2
answers
136
views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
- 41
4
votes
2
answers
243
views
Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?
I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?
Clarification:
Note that since the execution of the machine is not deterministic, ...
- 21.9k
4
votes
0
answers
26
views
Error correcting codes for transmitting a real value $x$ in [0,1], minimizing the reconstructed distance to the original $x$
I have been thinking a bit about error correcting codes, in particular the following problem:
Consider the problem of transmitting a single real number $x \in [0,1]$ over a lossy connection, where ...
- 41
4
votes
0
answers
101
views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
- 121
4
votes
0
answers
65
views
Signal-based Search
This is more of an open-ended information question, but to make it concrete, here's an example problem I have thought up:
Consider an $N\times N$ grid, $N$ odd, and consider that a single chunk of ...
- 378
3
votes
2
answers
514
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.1k
3
votes
1
answer
133
views
Randomized String Searching
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.
I want to state an algorithm that runs in time $O(n)$ where we assume that ...
- 641
3
votes
1
answer
659
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.
...
- 5,894
3
votes
1
answer
2k
views
Expected maximum bin load, for balls in bins with equal number of balls and bins [closed]
Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we ...
- 31
3
votes
2
answers
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
3
votes
1
answer
85
views
Is there a concept of probabilistic quantum computers?
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer
Quantum ...
- 413
3
votes
2
answers
133
views
Doesn't a quantum algorithm being deterministic contradict the superposition principle?
How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?
For ...
- 93