# 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
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". ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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., ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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?
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 ...
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 ...
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 ...
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 ...
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&...
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 ...
45 views

### Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
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 ?
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 ...
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 ...
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$ "...
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 ...
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 \...
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 ...
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 (...