As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [probabilistic-algorithms]

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

53 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
122 views

### Verify if array is orthogonal

Orthogonal arrays often appear in probabilistic algorithms. They can be efficiently constructed from, e.g., BCH codes. But is there an efficient algorithm that can verify if an array is orthogonal? I ...
• 125
68 views

### Noisy sorter: optimal algorithm

Given $n$ elements $x_1,\dots, x_n$, and algorithm $A$ which outputs $(r_1,\dots, r_n)=A(x_1,\dots, x_n)$, we say $A$ is $\epsilon$-sorting the list if $rank(x_i) \in (r_i-n\epsilon, r_i+ n\epsilon)$ ...
93 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 ...
• 4,959
92 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 ...
• 285
136 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 ...
• 151
102 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 ...
• 141
66 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 ...
• 1,731
168 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 ...
• 121
64 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$ ...
• 121
1 vote
33 views

### How can $R_HL$ differ from $RL$?

https://complexityzoo.net/Complexity_Zoo:R RL: Randomized Logarithmic-Space Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also ...
• 239
1 vote
46 views

### Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer

Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of ...
• 239
1 vote
39 views

### Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings

I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of. Setting: Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with ...
1 vote
68 views

### Weighted sample of ~k elements from array in O(n) time?

I have an array $a$ with $n$ elements, all of which have an associated weight. For example: $a = \{ (A,2), (B,5), (C,9), ..., (Z,1) \}$, such that element $A$ has weight $w_A=2$, element $B$ has ...
• 11
1 vote
24 views

### What are practical applications for markovs algorithm(string rewriting systems)

:) Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
1 vote
19 views

### Usage cases of AMS algorithm

This question is about the second frequency algorithm described in N. Alon, T. Matias, and M. Szegedy The space complexity of approximating the frequency moments. Specifically, I am asking about the ...
• 125
1 vote
25 views

### RP with very small error = P

I was asked to show the equality $RP(1 − 2^{-2^{n}}) = P$, which seems wrong to me (?). The $\supseteq$ direction is obvious, and I want to show the other direction. My first intuition was to run ...
• 161
1 vote
78 views

### Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M.$$ I have proven (and this is quite obvious) that ...
• 11
1 vote
19 views

### Distribution independence property testing

I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
1 vote
36 views

### Computing a threshold function

Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as $$g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x).$$ Let us be ...
• 219
1 vote