Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
167
questions
11
votes
1answer
332 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$-...
11
votes
0answers
349 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".
...
10
votes
2answers
611 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 ...
10
votes
1answer
505 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
...
10
votes
0answers
140 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 ...
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 ...
9
votes
2answers
490 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 ...
8
votes
1answer
254 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,...
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 ...
7
votes
2answers
1k 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 ...
7
votes
3answers
2k 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
2answers
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 ...
7
votes
1answer
2k 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 ...
7
votes
1answer
2k 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'...
7
votes
1answer
517 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 $\...
6
votes
1answer
361 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 ...
6
votes
1answer
169 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, ...
6
votes
1answer
308 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 ...
5
votes
2answers
4k 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 ...
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 ...
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 ...
5
votes
1answer
508 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 (...
5
votes
1answer
114 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 ...
5
votes
1answer
450 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 ...
5
votes
1answer
487 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 ...
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 ...
4
votes
2answers
469 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 $\...
4
votes
1answer
343 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 $\...
4
votes
2answers
100 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 ...
4
votes
2answers
363 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 (...
4
votes
1answer
221 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) ...
4
votes
1answer
580 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 ...
4
votes
1answer
297 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 ...
4
votes
2answers
99 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=...
4
votes
2answers
210 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, ...
4
votes
1answer
62 views
Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing though 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 who's ...
4
votes
0answers
88 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 ...
4
votes
0answers
57 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 ...
3
votes
1answer
132 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 ...
3
votes
1answer
658 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.
...
3
votes
2answers
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 ...
3
votes
2answers
120 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 ...
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, ...
3
votes
1answer
52 views
Is there a complexity class QPP?
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
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 ...
3
votes
1answer
67 views
Determine number of values less than mean in one pass through list
The problem statement is as follows:
Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ...
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:
...
3
votes
1answer
64 views
Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$
In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability ...
3
votes
1answer
111 views
A clarification on $PP$
Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following:
On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is ...
3
votes
1answer
133 views
Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions
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)) \...
