NC0 randomness vs. non-uniformity

Ask Question

Asked 1 year, 10 months ago

Modified 1 year, 10 months ago

Viewed 59 times

Ajtai and Ben-Or. A theorem on probabilistic constant depth Computations. STOC '84, 1984

Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.

Is there a similar relation known for probabilistic and non-uniform NC0? Or is it an open problem?

J. W. Tanner

8675 silver badges13 bronze badges

asked Feb 13, 2023 at 18:10

user499408

$\begingroup$ This question would be a better fit to cstheory.stackexchange.com $\endgroup$
– domotorp
Commented Feb 13, 2023 at 22:11
$\begingroup$ Hi @domotorp, thanks I posted it there (hope I am not making more mess by doing that.) cstheory.stackexchange.com/questions/52470/… $\endgroup$
– user499408
Commented Feb 13, 2023 at 23:39

Add a comment |

0