10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ They imply circuit lower bounds? $\endgroup$ – Nikhil Mar 17 '17 at 10:21
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.