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?

Improve this question
$\endgroup$
1
  • 2
    $\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
    Oct 14, 2021 at 13:33

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 16, 2021 at 9:58
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Oct 19, 2021 at 17:51
  • $\begingroup$ Since the question might be wrongly framed can you make the updates necessary to correct the BPLP part? $\endgroup$
    – Turbo
    Oct 19, 2021 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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