On the Power of Regular and Permutation Branching Programs

by Chin Ho Lee, Edward Pyne, and Salil Vadhan

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.

See ECCC TR23-102.

Back to list of Oded's choices.