Questions tagged [randomized-algorithms]
An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
215
questions
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 ...
- 11k
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 ...
- 877
36
votes
1
answer
3k
views
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \...
- 21.8k
33
votes
9
answers
2k
views
Randomized algorithm that "looks" deterministic?
Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness ...
- 7,020
28
votes
10
answers
2k
views
Probabilistic (randomized) algorithms before "modern" computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In ...
28
votes
1
answer
1k
views
Is uniform RNC contained in polylog space?
Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL). Is log-space-uniform RNC also in this class? The standard randomized version of PolyL should be in PolyL, ...
- 1,811
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 ...
- 19.1k
27
votes
1
answer
921
views
Other applications of Karger-Stein branching amplification?
I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don'...
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 ...
- 638
24
votes
1
answer
646
views
The randomized query complexity of the conjoined trees problem
An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
- 13.8k
23
votes
3
answers
3k
views
Generalizing the "median trick" to higher dimensions?
For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta > 0$, at the cost of only a ...
- 4,481
22
votes
2
answers
2k
views
Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?
If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\...
- 2,747
22
votes
2
answers
3k
views
Yao's Minimax Principle on Monte Carlo Algorithms
The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set $...
21
votes
1
answer
729
views
A flowchart for concentration bounds
When I teach tail bounds, I use the usual progression:
If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's ...
- 32.2k
20
votes
2
answers
656
views
Estimating Average in Polynomial Time
Let $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ be a function. We want to estimate the average of $f$; that is: $\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$.
...
- 16.6k
19
votes
3
answers
700
views
Running a BPP algorithm with a half-random, half-adversarial string
Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary ...
- 13.8k
18
votes
3
answers
821
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 ...
- 951
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 ...
- 16.6k
18
votes
2
answers
985
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 ...
- 3,828
18
votes
3
answers
815
views
In what class are randomized algorithms that err with exactly 25% chance?
Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/...
- 14.1k
18
votes
1
answer
1k
views
The complexity of sampling (approximately) the Fourier transform of a Boolean function
One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.
Here and ...
- 6,083
17
votes
3
answers
729
views
Randomize or Not?
This question is inspired by the Georgia Tech Algorithms and Randomness Center's t-shirt, which asks "Randomize or not?!"
There are many examples where randomizing helps, especially when operating in ...
- 12k
16
votes
5
answers
2k
views
Examples of successful derandomization from BPP to P
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?
The only example that comes ...
user34945
16
votes
2
answers
977
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 $...
- 11.2k
15
votes
2
answers
1k
views
Which randomized algorithms have exponentially small error probability?
Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized ...
- 11k
15
votes
1
answer
470
views
Natural theorems proven only "to high probability"?
There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.
Question: Are there any natural ...
- 3,263
15
votes
2
answers
585
views
Reusing 5-independent hash functions for linear probing
In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (...
- 11.2k
14
votes
1
answer
490
views
Is it enough for linear program constraints to be satisfied in expectation?
In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
- 1,591
14
votes
1
answer
356
views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence ...
- 16.6k
14
votes
1
answer
461
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 ...
- 6,775
13
votes
4
answers
645
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]$ ...
- 14.1k
13
votes
2
answers
969
views
What is the proof of this nonstandard version of Azuma's inequality?
In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:
Let $C_1, \dots, C_k$ be real-valued ...
- 1,753
13
votes
2
answers
687
views
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Definition. A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability.
Question. The notion of a ...
- 133
12
votes
5
answers
3k
views
List of quantum-inspired algorithms
Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:
A quantum-inspired classical ...
12
votes
1
answer
3k
views
Count $k$-hop neighborhood for every vertex
For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
- 121
12
votes
0
answers
223
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 ...
- 650
11
votes
2
answers
886
views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
- 5,616
11
votes
2
answers
870
views
A converse to Fano's inequality ?
Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:
Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is ...
- 32.2k
11
votes
1
answer
352
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 ...
- 1,002
11
votes
2
answers
630
views
Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$
I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
- 4,481
11
votes
1
answer
323
views
Randomized Polynomial Hierarchy?
I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?
It seems, we could still build a hierarchy, the same ...
- 11.4k
11
votes
0
answers
202
views
On preprocessing a convex polyhedron prior to sampling
Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that
$$ B \subset TK \tilde{\subset}\ \...
- 32.2k
10
votes
3
answers
649
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 ...
- 549
10
votes
1
answer
462
views
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...
- 3,083
10
votes
2
answers
319
views
What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?
I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject ...
- 101
10
votes
1
answer
576
views
What is the advantage of designing deterministic distributed algorithms?
Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.
Paxos is deterministic in the sense that given the ...
- 201
10
votes
1
answer
2k
views
What is the worst case of the randomized incremental delaunay triangulation algorithm?
I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$.
There is an exercise which ...
- 203
10
votes
2
answers
548
views
Exact formula for the number of spanning trees of a rectangle
This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
- 568
10
votes
1
answer
556
views
Determine the minimum number of coin-weighings
In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.
...
- 746
10
votes
2
answers
806
views
How to shuffle colour balls?
I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical)
i need an efficient shuffling algorithm, so ...
- 271