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
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 ...
Zix's user avatar
  • 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$-...
jmite's user avatar
  • 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". ...
Karolis Juodelė's user avatar
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 ...
Student's user avatar
  • 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 ...
Robert777's user avatar
  • 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 ...
Martin Berger's user avatar
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 ...
Michael's user avatar
  • 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 ...
Numerator's user avatar
  • 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 ...
somebody's user avatar
  • 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 ...
Nick Anderegg's user avatar
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,...
hengxin's user avatar
  • 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 ...
iart's user avatar
  • 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'...
Anonymous's user avatar
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 ...
Niklas Rosencrantz's user avatar
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 ...
nicolas's user avatar
  • 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 ...
user6818's user avatar
  • 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 ...
Igglyboo's user avatar
  • 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 $\...
Queue's user avatar
  • 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, ...
advocateofnone's user avatar
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, ...
user avatar
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 ...
LMG's user avatar
  • 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 ...
Jake's user avatar
  • 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 ...
john mangual's user avatar
  • 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) ...
dpalma's user avatar
  • 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 ...
Simd's user avatar
  • 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 (...
user95224's user avatar
  • 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 ...
Varun's user avatar
  • 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 ...
babou's user avatar
  • 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 ...
Vitaly Olegovitch's user avatar
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 ...
user220201's user avatar
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 $\...
Richard's user avatar
  • 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 ...
guest's user avatar
  • 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 $\...
Uri's user avatar
  • 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 (...
tparker's user avatar
  • 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 $...
kings's user avatar
  • 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: ...
woz's user avatar
  • 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 ...
ranys's user avatar
  • 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 ...
Enno Shioji's user avatar
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=...
John T.L's user avatar
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, ...
Kaveh's user avatar
  • 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 ...
almostuseful's user avatar
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 ...
Ali's user avatar
  • 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 ...
torquestomp's user avatar
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$ ...
David Richerby's user avatar
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 ...
user1374864's user avatar
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. ...
Erel Segal-Halevi's user avatar
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 ...
user3367692's user avatar
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 ...
Aadith Ramia's user avatar
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 ...
porton's user avatar
  • 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 ...
Alex Michael's user avatar

1
2 3 4 5