Questions tagged [randomized-algorithms]
Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.
452 questions
3
votes
1
answer
102
views
Is Exact Matching with more than two colours in RP or NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 879
3
votes
1
answer
118
views
Stateless Modeling of Stochastic Systems
Let $f : S \times \mathbb{N} → \mathbb{Z}$ be a stochastic function seeded by $\mathrm{seed} \in S$, constrained such that
$$
|f(\mathrm{seed}, t + 1) - f(\mathrm{seed}, t)| \le 1
$$
Such a function ...
- 203
0
votes
0
answers
65
views
What is the name and theoretical basis for a Treap/RBST variant with a probabilistic, size-based merge?
I'm exploring data structures suitable for persistent applications. A key use case I have is splitting a subsegment from a tree, copying it, and then merging these copies into other data structures.
...
- 1
1
vote
0
answers
29
views
Asymptotically optimal strategy for Las Vegas algorithms with unknown run time distribution if you can suspend and resume later
In the paper "Optimal Speedup of Las Vegas Algorithms" Luby, M., Sinclair, A. and Zuckerman, D. give an asymptotically optimal sequences for how many time to run an Las Vegas algorithm ...
- 225
1
vote
1
answer
86
views
What do you call the two most common ways of selecting a random leaf node from a tree?
If you have a tree, there are two common ways to select a random leaf node from the tree:
You can "flatten" out the tree, so that each leaf node gets selected with the same probability.
...
- 11
2
votes
0
answers
91
views
Given a polynomial time approximation for expected chromatic number of random graph, can we show that P = NP?
Consider an Erdos-Renyi random graph $G(n, p)$. Suppose there exists a coloring algorithm $\mathcal{A}$ that, for any graph instance $g \sim G(n, p)$, generates a valid coloring $C^{\mathcal{A}}_g$ of ...
- 348
1
vote
1
answer
103
views
Randomised Algorithm for Maximum Matching
Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithm
has $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−
1}$. We ...
- 21
0
votes
0
answers
80
views
Hardness of approximation for complexity class $\mathsf{MA}$
Under the derandomization assumption $\mathsf{MA=NP}$, one can obtain the hardness of approximation result for the class $\mathsf{MA}$. (Note: By invoking the PCP theorem.)
Has there been another way/...
- 229
0
votes
1
answer
74
views
Efficient algorithm for generating a random number in [1, 50000] with 40% probability for a fixed value (12345) and uniform distribution elsewhere?
Consider an algorithm that generates random numbers in the range [1, 50000] with the following distribution:
The specific value 12345 should have a 40% probability of being selected
The remaining 60% ...
2
votes
0
answers
79
views
Find the random bits that used by Turing machine
Let $𝐿 ∈ RTIME(𝑛 ^3 )$. That is: There exists a Probabilistic TM that runs in $𝑂(𝑛^3 )$ time, such that for every $𝑥 ∈ \{0,1\}^∗$
$x ∈ L ⟹ Pr[𝑀(𝑥) = 1] ≥ 2/3$
$x ∉ L ⟹ Pr[𝑀(𝑥) = 0] = 1$
I ...
- 121
0
votes
0
answers
154
views
BPP Closure Under Concatenation
I'm trying to prove that BPP is closed under concatenation, meaning that if $A,B \in BPP$, then $AB = \{ab|a\in A,b\in B\} \in BPP$.
EDIT: I think I've made it:
BPP is Closed Under Concatenation
Let $...
1
vote
0
answers
128
views
Inapproximability of Maximum Independent Set
Lemma1. There exists a polynomial time computable transformation $f$ from the 3CNF formulas to graphs such that for every 3CNF formula $\varphi$, $f(\varphi)$ is an $n$-vertex graph whose $|MIS| = \...
- 109
1
vote
0
answers
59
views
probabilistic polynomial-time Turing machine with advice string construction
Let $L \subseteq \{0, 1\}^∗$ be a language and $M_L$ be a probabilistic polynomial-time Turing machine(PPTM), such that, for every $x \in\{0, 1\}^n$ the machine $M$ uses at most $n^{1/4}$
random coins ...
- 109
0
votes
0
answers
118
views
BPP vs PP and error amplification
I try to understand the difference between complexity classes PP and BPP for randomized algorithms. I follow this question which is quite old, so I prefer to open another thread. Surprisingly, I could ...
- 151
1
vote
1
answer
159
views
Deleting the randomness in the proof of $BPP\subseteq EXP$
The proof for $BPP\subseteq EXP$, goes like this:
Let $L\in BPP$, meaning $L$ has a randomized TM $M$ that runs in some $k = poly(n)$.
Thus, $M$ can read at most $k$ bits from a random string $r\in\...
- 341