Questions tagged [randomized-algorithms]

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

Filter by
Sorted by
Tagged with
39 votes
9 answers
4k views

Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
adrianN's user avatar
  • 877
27 votes
4 answers
2k views

What specific evidence is there for P = RP?

RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
András Salamon's user avatar
18 votes
3 answers
816 views

Does randomness buy us anything inside P?

Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$. Do we know of any problem $Q \in \mathsf{P}$ such ...
aelguindy's user avatar
  • 951
41 votes
7 answers
5k views

When does randomization speed up algorithms and it "shouldn't"?

Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic ...
Dana Moshkovitz's user avatar
26 votes
1 answer
2k views

Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$. The implementation of the algorithm in computers ...
Jérémie's user avatar
  • 638
18 votes
2 answers
976 views

Are theoretically sound pseudorandom generators used in practice?

As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
Henry Yuen's user avatar
  • 3,788
18 votes
2 answers
2k views

Beginner's Guide to Derandomization

I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented. I'm new to the subject of "Derandomization," and as such, I wanted ...
Sadeq Dousti's user avatar
  • 16.5k
16 votes
2 answers
960 views

Faster join of treap-like data structures with approximately the same size

Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $...
jbapple's user avatar
  • 11.2k
14 votes
1 answer
455 views

Adleman's theorem over infinite semirings?

Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
Stasys's user avatar
  • 6,765
13 votes
4 answers
644 views

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model: We can get integers uniformly random from $[1,2^n]$ ...
domotorp's user avatar
  • 13.9k
11 votes
1 answer
336 views

Randomness and small circuits complexity classes

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide ...
C.P.'s user avatar
  • 992
10 votes
3 answers
645 views

What is the fastest known simulation of BPP using Las Vegas algorithms?

$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes. $\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
echuly's user avatar
  • 549
8 votes
3 answers
674 views

Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor? In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...
jbapple's user avatar
  • 11.2k
7 votes
2 answers
2k views

Random sampling data structure with removal

I'd like a data structure with the following operations: create a new instances from an array of floating point weights. randomly sample, returning an item with probability proportionate to its ...
DRMacIver's user avatar
  • 434
7 votes
1 answer
652 views

Shortest paths perturbation

I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
Matteo's user avatar
  • 569
7 votes
2 answers
512 views

What bound can we get using $k$-th moment inequality under 3-wise independence?

Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)...
Amos's user avatar
  • 201
7 votes
4 answers
642 views

How to shuffle cards with restrictions?

I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied. For example, i would like to shuffle 4 decks of cards, and make sure: Any consecutive 4 ...
colinfang's user avatar
  • 271
6 votes
1 answer
727 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, . . ....
Peng Zhang's user avatar
  • 1,453
3 votes
2 answers
162 views

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by \begin{eqnarray} \langle x,y\rangle_{\...
dohmatob's user avatar
  • 291