# 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? Oct 14 at 13:33

(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).
• Welcome to cstheory, TedP! What do you mean with "ordered branching programs capture ... a logspace machine"? We have $\text{Logspace}_{/poly}=\text{BP}$ where $\text{BP}$ is the class of polynomial-width polynomial-depth read-many Branching Programs. The restriction of read-once is non-trivial. For example, a Logspace machine can compute the Hidden Weighted Bit function, but an ordered read-once branching program cannot. So In that sense, ordered read-once BPs capture only a strict subset of logspace machines. Oct 16 at 9:58