# Derandomizing arbitrary width *read-many* and *ordered* branching programs?

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?

• 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? yesterday

(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).