0
$\begingroup$

Modifying following TedP

We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered branching programs is equivalent to $BPLP=L$ where $BPLP$ is class programs which are in two sided error based randomized logarithmic space and terminate in deterministic polynomial time.

What are derandomizing width $k=f(n)$ two-sided error 1) read many with $f(n)\in\omega(1)$ and 2) read once ordered with $f(n)\in o(n)$ randomized branching programs equivalent to?

$\endgroup$
1
  • 1
    $\begingroup$ Not sure why it is downvoted, but maybe the wording could be clarified to explain what "derandomizing X is equivalent to [equivalence of two classes]" means. Does "derandomizing X" mean that randomized branching programs with X decide the same languages as deterministic branching programs with X? $\endgroup$
    – Neal Young
    yesterday
1
$\begingroup$

(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching programs (a subset of read-once branching programs where the input variables are read in a known fixed order) capture the behavior of a logspace machine over its random bits (so an optimal PRG for such implies $BPL=L$). There is extensive work on derandomizing small-width ordered BPs, and in some restricted classes we have near-optimal constructions (for large error).

New contributor
TedP is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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