On the Power of Regular and Permutation Branching Programs

Oded's comments

Not having followed this area closely, I found the abstract hard to digest, and postponed looking at the paper for a few days. I was delighted to find the introduction extremely clear and reader-friendly (which is unfortunately rare in ToC), so I urge the non-experts to skip the abstract and read the introduction: Reading the first two pages, you will get an excellent overview of this important research direction as well as a clear statement of the main result (i.e., Thm 1.7).

Thm 1.7 refers to the relative power of general versus regular standard-order ROBP (hereafter denoted SOBP), where standard-order means that at time $i$ the BP reads the input bit $i$, and regular means that each vertex (except the start vertex) has in-degree 2. Thm 1.7 asserts that for width $w \geq 4$, the general model (i.e., general SOBP) can be emulated by the restricted model (i.e., regular model) by increasing the width by a factor that is linear in the input length.

Unlike prior results, the emulation here is worst-case (i.e., works for all inputs rather than average-case). This allows to obtain corollaries such as 1.8 and 1.9, where Cor 1.8 asserts that weighted PRGs that fool regular SOBPs (of width $w$ and length $m$) can be used to fool general SOBPs (of width $w/m$ and length $m$).

Another result that I find very interesting is a separation between the power of regular SOBPs and permutation SOBPs, where in the latter SOBP the labeling of directed edges (by the corresponding input-bits) yields a 2-coloring of the BP (wrt in-coming edges). The results here (i.e., Thm 1.11-1.12) assert that inner-product-mod-2, which can be computed by a regular SOBP of width four, is extremely hand for permutation ROBPs (not only SOBRs). Specifically, hardness is in the average-case sense, where for SOBPs having any constant advantage over guessing (e.g., success probability 0.51) requires exponential width (see Thm 1.11), and for ROBPs this holds (``only'') for success probability exceeding $0.76$ (see Thm 1.12).

The last result that I will review is Prop 1.14, which should be named a theorem. It asserts that permutation ROBP of constant width can compute a function that cannot be computed (in the worst-case) by general SOBP of sub-exponential width. That is, while Thm 1.12 asserts that regular SOBPs cannot be efficiently emulated by permutation ROBPs, the current result asserts that the opposite emulation fails too.

The original abstract

We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation.

• Regular SOBPs of length $n$ and width $\lfloor w(n+1)/2\rfloor$ can exactly simulate general SOBPs of length $n$ and width $w$, and moreover an $n/2-o(n)$ blow-up in width is necessary for such a simulation.

  Our result extends and simplifies prior average-case simulations (Reingold, Trevisan, and Vadhan (STOC 2006), Bogdanov, Hoza, Prakriya, and Pyne (CCC 2022)), in particular implying that weighted pseudorandom generators (Braverman, Cohen, and Garg (SICOMP 2020)) for regular SOBPs of width $\text{poly}(n)$ or larger automatically extend to general SOBPs. Furthermore, our simulation also extends to general (even read-many) oblivious branching programs.

• There exist natural functions computable by regular SOBPs of constant width that are average-case hard for permutation SOBPs of exponential width. Indeed, we show that Inner-Product mod $2$ is average-case hard for arbitrary-order permutation ROBPs of exponential width.
• There exist functions computable by constant-width arbitrary-order permutation ROBPs that are worst-case hard for exponential-width SOBPs.
• Read-twice permutation branching programs of subexponential width can simulate polynomial-width arbitrary-order ROBPs.

See ECCC TR23-102.