<p>The class uniform-RNC has been studied a lot. 
It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and polylogarithmic running time (see the Handbook of Theoretical Computer Science Vol. A). So the question is whether every efficient randomised parallel algorihm can be derandomized.</p>

<p>Since symbolic determinant identity testing is in uniform-RNC, derandomizing RNC implies circuit lower bounds by the results of Kabanets &amp; Impagliazzo (Computational Complexity, 13(1-2), pages 1-46, 2004).</p>

<p>An important special case is the question whether we can compute perfect matchings in uniform-NC. There are several randomized parallel algorithms known, but we do not know whether there is a deterministic one. Recently,
Fenner, Gurjar and Thierauf (STOC 2016) have shown that we can compute perfect matchings in bipartite graphs by uniform circuits of polylogarithmic depth and quasipolynomial size.</p>

CC BY-SA 3.0
2017-03-17T10:45:07.033Z
2017-03-17T10:45:07.033Z
Markus Bläser
<p>Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. More formally we provide polynomially many random bits and we accept an input iff the probability to accept is over $\frac{2}{3}$.</p>

<p>In a <a href="https://cstheory.stackexchange.com/questions/37741/randomness-and-small-circuits-complexity-classes/37764#37764">previous post</a>, I asked if it was known whether the equality holds between  $\mathcal{C}$ and $\textrm{BP-}\mathcal{C}$ for $\mathcal{C}$ a circuit complexity class. The answer is yes for all complexity classes expressive enough to compute Majority and for $\textrm{AC}^0$ for some other reason. 
Those results are however non-uniform and I would like to know:</p>

<ol>
<li><p>Are uniform versions of those results studied or known? Any partial results ?</p></li>
<li><p>Do they imply long standing conjecture? </p></li>
</ol>

<p>I believe that uniform derandomisation of $\textrm{P}/\textrm{poly}$ is exactly $\textrm{P}=\textrm{BPP}$ so I expect the answer to be "yes" but it is less clear to me what uniform derandomisation of small classes within the $\textrm{NC}$-hierarchy would imply.</p>

CC BY-SA 3.0
2017-03-17T10:21:36.533Z
They imply circuit lower bounds?
Nikhil
<circuit-complexity><randomized-algorithms><derandomization>
Uniform derandomisation of circuit complexity classes
C.P.
# Uniform derandomisation of circuit complexity classes

(Asked by: username_0 on 2017-03-17)

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. More formally we provide polynomially many random bits and we accept an input iff the probability to accept is over $\frac{2}{3}$.

In a [previous post](https://cstheory.stackexchange.com/questions/37741/randomness-and-small-circuits-complexity-classes/37764#37764), I asked if it was known whether the equality holds between $\mathcal{C}$ and $\textrm{BP-}\mathcal{C}$ for $\mathcal{C}$ a circuit complexity class. The answer is yes for all complexity classes expressive enough to compute Majority and for $\textrm{AC}^0$ for some other reason.
Those results are however non-uniform and I would like to know:

1. Are uniform versions of those results studied or known? Any partial results ?
2. Do they imply long standing conjecture?

I believe that uniform derandomisation of $\textrm{P}/\textrm{poly}$ is exactly $\textrm{P}=\textrm{BPP}$ so I expect the answer to be "yes" but it is less clear to me what uniform derandomisation of small classes within the $\textrm{NC}$-hierarchy would imply.

**Tags:** circuit-complexity, randomized-algorithms, derandomization
> **Comments:**
> **username_1**: They imply circuit lower bounds?  

---

## 1 answers

### Answer by username_2 on 2017-03-17. Score: 6 | Accepted answer

The class uniform-RNC has been studied a lot.
It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and polylogarithmic running time (see the Handbook of Theoretical Computer Science Vol. A). So the question is whether every efficient randomised parallel algorihm can be derandomized.

Since symbolic determinant identity testing is in uniform-RNC, derandomizing RNC implies circuit lower bounds by the results of Kabanets & Impagliazzo (Computational Complexity, 13(1-2), pages 1-46, 2004).

An important special case is the question whether we can compute perfect matchings in uniform-NC. There are several randomized parallel algorithms known, but we do not know whether there is a deterministic one. Recently,
Fenner, Gurjar and Thierauf (STOC 2016) have shown that we can compute perfect matchings in bipartite graphs by uniform circuits of polylogarithmic depth and quasipolynomial size.


---

