# Questions tagged [randomized-algorithms]

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

167 questions
4k 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 ...
2k views

2k views

1k 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 ...
912 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 ...
336 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 ...
414 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 ...
295 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 of BPP ...
394 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. (...
301 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 ...
503 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]$ ...
227 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 ...
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 ...
516 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$ ...
195 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}\ \...
546 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 ...
615 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 ...
391 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 ...
279 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 ...
509 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 ...
220 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 ...
431 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 ...
283 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 ...
511 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. ...
615 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 ...
133 views

### Examples of the use of biased estimators

Biased estimators are useful in statistics because they can optimize mean-squared error more than what an unbiased estimator can manage. I was wondering if in theoryCS if there are any very notable ...
264 views

### What are some results on algorithms that estimate polynomials over a given set of points?

There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of ...
305 views

### Find an approximate argmax using only approximate max queries

Consider the following problem. There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a ...
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 ...