Uniform derandomisation of circuit complexity classes

Question

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, 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.

Answer 1

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.