# Questions tagged [randomized-algorithms]

An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.

49 questions
308 views

### Algorithm to compute distance between powers

Given coprime $a, b$, can you quickly compute $$\min_{x, y > 0} |a^x - b^y|$$ Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
541 views

### Can this randomized greedy algorithm be made online? Or being proved impossible?

I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring. Offline: The potential colors are ordered 1, 2, . . ....
216 views

### Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
195 views

11 views

### Is there a stochastic/online version of the GLM-Tron algorithm?

The GLM-Tron algorithm appeared in Theorem $1$ in this paper, https://arxiv.org/pdf/1104.2018.pdf Is there a stochastic version of this? (...essentially something that will randomly sample a few ...
86 views

### distNP-complete problem

Here on page 367 there is an example of $\text{dist}\mathbb{NP}$-complete problem: let $U$ contain all tuples $\langle M,x,1^t\rangle$ where there exists a string $y\in \{0,1\}^l$such that the ...
28 views

### Expected size of the min-cut, under edge perturbations

Suppose we have a graph $G(V, E)$. Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$. Create a random modification of the graph: Drop each ...
212 views

### Steiner Tree and minimum spanning tree

If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
### $BPP$ before Adleman-Sipser-Gacs theorem?
Where was $BPP$ before it was in second level? If we show $BPP$ is in $P^{NP}$ then we would've separated $BPP$ from $EXP^{NP}$. What did $BPP$ in second level accomplish? Did it have to cross any ...