# Tag Info

### 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")...
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" ...

### 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 ...
Accepted

### The relationship between degree of vertex and size of dominating set

1) To refine daniello's answer, there is a standard bound in domination that for any graph of minimum degree $d$, there is a dominating set of size at most (roughly) $\frac{\log d}{d}n$. This bound ...
Here is a straightforward reduction from the max-cut problem: Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a ...