Questions tagged [probabilistic-algorithms]

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

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
342 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
0answers
139 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 ...
4
votes
1answer
58 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
75 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
0answers
38 views

Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?

$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that ...
3
votes
0answers
59 views

Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
2
votes
0answers
41 views

Correctness of Karger's min-cut Algorithm

tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
2
votes
0answers
80 views

Stochastic Computing: What is “Bundle Processing”?

I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says: Bundle Processing involves sending a fixed number of bits instead of a stream. One of the ...
2
votes
0answers
62 views

Box labelling game

I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$. I have infinite supply of boxes. Box labelling game: I pick a random sticker ...
2
votes
0answers
104 views

What is the meaning of the output weights of a Conditional Random Field (CRF) model?

Problem When train my linear chain CRF with annotated observations, I feed it with a number of sequences containing observation values and a "ground-truth" label for each observation. I'm currently ...
2
votes
0answers
58 views

Approximate target subset by intersecting other subsets

Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ ...
1
vote
0answers
22 views

Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?

Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$. Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., ...
1
vote
0answers
190 views

Perfect Completeness of AM protocols?

I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...
1
vote
0answers
32 views

Probability lower bound on a double cycle on two vertices in random cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
1
vote
0answers
22 views

Extracting room voids in a house

I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house. In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
1
vote
0answers
34 views

Probabilistic linebreaking algorithm

I'm currently trying to implement this paper. Based on a bayesian network, the paper stays unclear about how to ultimately use it's content ("straightforward inference"). But after a lot of ...
1
vote
0answers
56 views

Finding subset of integer summing up above threshold

Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
1
vote
0answers
88 views

distinguishing two biased coins

I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
1
vote
0answers
71 views

How to select cuckoo filter parameters?

If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?
1
vote
0answers
37 views

What's the polynomial involved in the PCP theorem?

Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?
1
vote
0answers
31 views

What does ∇log mean in the Robbins-Montro algorithm?

The Robbins/Monro Algorithm is a type of stochastic optimization algorithm of the following form: (as mentioned in wikipedia) $$x_{n+1} - x_n = a_n(\alpha - N(x_n))$$ where $M(x) = \alpha$ is a ...
1
vote
0answers
66 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
1
vote
0answers
388 views

PageRank and EigenTrust: How small should epsilon be?

For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or ...
1
vote
1answer
45 views

Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?

Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice ...
0
votes
1answer
20 views

Probability of loss using a binary symmetric channel

Today we talked about Information Theory and the binary symetric channel. For newbies here is a little explanation : For instance if I want to send a binary to someone : The bit will be "flipped&...
0
votes
0answers
17 views

Reference on PCP theorem

Can someone recommend a reference on the PCP theorem that explains how it works via examples rather than formal CS language? Specifically, I'm looking for the example on how graph colouring can be ...
0
votes
0answers
45 views

Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
0
votes
0answers
23 views

Chernoff Bounds (upper tail)

For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 . Like in this paper ([see this link ]) 1. Can you tell me why ?
0
votes
0answers
71 views

Prove an estimator

Consider an undirected graph $G=(V,E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
0
votes
0answers
14 views

What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?

I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I ...
0
votes
0answers
34 views

Construction of hash function with a given distribution

Two questions about the construction of a hash function: Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
0
votes
0answers
28 views

PCP variant in P with non 0 randomness and polynomial proof

I am trying to show that a particular language $L$ in PCP(log,q) is also in P. The PCP protocol works as follows: log many random bits and checks at q positions in a polynomial length proof. The ...
0
votes
0answers
47 views

Show that if language belongs to $BPP$ then also similar language belgons to $QP$

Prove that for each arbitrary set of natural numbers $A$ we have: $$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin (n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \...
0
votes
0answers
53 views

find a values of a array members

We have Some big hashed array of data with boolean values, we know keys, but don't know values. Oracle who have input of array of keys and can tell how much of them are ...
0
votes
0answers
127 views

Algorithm to sort elements of an array under uncertainty

I have an array of $n$ elements. Each element is basically the mean of gamma distribution and the actual value of the element is picked from that distribution. Assume the parameters of distribution (...
-1
votes
1answer
111 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 ...