<p>(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 <em>read many</em> branching programs capture <span class="math-container">$NC_1$</span>, and width poly<span class="math-container">$(n)$</span> <em>ordered</em> 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 <span class="math-container">$BPL=L$</span>). There is extensive work on derandomizing small-width ordered BPs, and in some restricted classes we have near-optimal constructions (for large error).</p>

CC BY-SA 4.0
2021-10-16T09:58:00.010Z
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.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2021-10-19T17:51:50.387Z
O(1) width read many bp is NC1 while poly (n) width read many bp is L/poly. Thank you and these are the kind of classifications I was looking for.
Turbo
CC BY-SA 4.0
2021-10-19T17:53:10.633Z
Since the question might be wrongly framed can you make the updates necessary to correct the BPLP part?
Turbo
CC BY-SA 4.0
2021-10-14T14:54:34.990Z
2021-10-14T15:00:25.280Z
2021-10-14T15:00:25.280Z
TedP
<p><strong>Modifying following TedP</strong></p>
<p>We know that derandomizing width <span class="math-container">$5\leq k\in O(1)$</span> read many branching programs is equivalent to <span class="math-container">$BPNC^1=NC^1$</span> and derandomizing width <span class="math-container">$k\in\Omega(n)$</span> read once ordered branching programs is equivalent to <span class="math-container">$BPLP=L$</span> where <span class="math-container">$BPLP$</span> is class programs which are in two sided error based randomized logarithmic space and terminate in deterministic polynomial time.</p>
<blockquote>
<p>What are derandomizing width <span class="math-container">$k=f(n)$</span> two-sided error 1) read many with <span class="math-container">$f(n)\in\omega(1)$</span> and 2) read once ordered with <span class="math-container">$f(n)\in o(n)$</span> randomized branching programs equivalent to?</p>
</blockquote>

CC BY-SA 4.0
2021-10-14T13:33:55.450Z
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?
Neal Young
<cc.complexity-theory><randomness><derandomization><space-bounded><pseudorandom-generators>
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Turbo
# Derandomizing arbitrary width *read-many* and *ordered* branching programs?

(Asked by: username_0 on 2021-10-14)

**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?

**Tags:** cc.complexity-theory, randomness, derandomization, space-bounded, pseudorandom-generators
> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2021-10-14. Score: 1

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

> **Comments:**
> **username_3**: 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.  
> **username_0**: O(1) width read many bp is NC1 while poly (n) width read many bp is L/poly. Thank you and these are the kind of classifications I was looking for.  
> **username_0**: Since the question might be wrongly framed can you make the updates necessary to correct the BPLP part?  

---

