# Tag Info

## Hot answers tagged randomized-algorithms

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

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best ...
• 14.7k
Accepted

### The randomized query complexity of the conjoined trees problem

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ ...
• 236

### Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
• 6,997

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

An old example is volume computation. Given a polytope described by a membership oracle, there's a randomized algorithm running in polynomial time to estimate its volume to a $1+\epsilon$ factor, but ...
• 31.7k

### Which randomized algorithms have exponentially small error probability?

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, ...
• 10.7k
Accepted

### Generalizing the "median trick" to higher dimensions?

What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" ...
• 50.2k

### Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
• 8,546