Seems quite a day: Waking-up in the morning and seeing three recent posts of interesting papers within one's areas of interest. Needless to say, I did not read any of these works yet, beyond their abstracts, but the abstracts are fascinating enough for me to decide to recommend these works for reading. In light of these exceptional circumstances, I'm not making comments on any of these papers, but rather list their abstracts below.
1. Monotone Branching Programs: Pseudorandomness and Circuit Complexity by Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan (posted as ECCC TR21-018).
Abstract
We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.
We prove that constant-width monotone branching programs of polynomial size are equivalent in power to $AC^{0}$ circuits. This complements the celebrated theorem of Barrington, which states that constant-width branching programs, without the monotonicity constraint, are equivalent in power to $NC^{1}$ circuits.
Next we turn to read-once monotone branching programs of constant width, which we note are strictly more powerful than read-once $AC^0$. Our main result is an explicit pseudorandom generator that $\varepsilon$-fools length $n$ programs with seed length $\widetilde{O}(\log(n/\varepsilon))$. This extends the families of constant-width read-once branching programs for which we have an explicit pseudorandom generator with near-logarithmic seed length.
Our pseudorandom generator construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions [AW89,GMRTV12]. We give a randomness-efficient width-reduction process which allows us to simplify the branching program after only $O(\log\log n)$ independent applications of the Forbes--Kelley pseudorandom restrictions [FK18].
2. Pseudodistributions That Beat All Pseudorandom Generators by Edward Pyne and Salil Vadhan (posted as ECCC TR21-019).
Note: What this paper calls pseudorandom pseudodistribution generator (PRPG) is called weighted pseudorandom generators (WPRGs) in the next paper (i.e., Nr. 3). We prefer the latter term.
Oded's comment: I wish to highlight the fact that this work presents a (non-contrived) seperation between weighted pseudorandom generators and ordinary pseudorandom generators. Furthermore, the separation is shown using an explicit construction of a WPRG and refers to a natural class of distinguishers. The fact that WPRGs suffice for derandomization implies that there are classes of algorithms that can be derandomized although ordinary PRGs cannot be used for that purpose.
Abstract
A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ordered branching programs whose seed length has a better dependence on the error parameter $\epsilon$ than the classic PRG construction of Nisan (STOC 1990 and Combinatorica 1992).
In this work, we give an explicit construction of PRPGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a PRPG for ordered permutation branching programs of unbounded width with a single accept state that has seed length $\tilde{O}(\log^{3/2} n)$ for error parameter $\epsilon=1/\text{poly}(n)$, where $n$ is the input length. In contrast, recent work of Hoza et al. (ITCS 2021) shows that any PRG for this model requires seed length $\Omega(\log^2 n)$ to achieve error $\epsilon=1/\text{poly}(n)$.
As a corollary, we obtain explicit PRPGs with seed length $\tilde{O}(\log^{3/2} n)$ and error $\epsilon=1/\text{poly}(n)$ for ordered permutation branching programs of width $w=\text{poly}(n)$ with an arbitrary number of accept states. Previously, seed length $o(\log^2 n)$ was only known when both the width and the reciprocal of the error are subpolynomial, i.e. $w=n^{o(1)}$ and $\epsilon=1/n^{o(1)}$ (Braverman, Rao, Raz, Yehudayoff, FOCS 2010 and SICOMP 2014).
The starting point for our results are the recent space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadenijad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving PRPGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (personal communication, January 2021).
3. Error Reduction For Weighted PRGs Against Read Once Branching Programs by Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma (posted as ECCC TR21-020).
Abstract
Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and Liao [CL20] somewhat simplified the technically involved BCG construction, also obtaining some improvement in parameters.
In this work we devise an error reduction procedure for PRGs against ROBPs. More precisely, our procedure transforms any PRG against length n width w ROBP with error 1/poly(n) having seed length s to a WPRG with seed length s + O(log(w/?)loglog(1/?)). By instantiating our procedure with Nisan’s PRG [Nis92] we obtain a WPRG with seed length O(log(n)log(nw) + log(w/?)loglog(1/?)). This improves upon [BCG20] and is incomparable with [CL20].
Our construction is significantly simpler on the technical side and is conceptually cleaner. Another advantage of our construction is its low space complexity O(log nw)+ poly(loglog(1/?)) which is logarithmic in n for interesting values of the error parameter ?. Previous constructions (like [BCG20, CL20]) specify the seed length but not the space complexity, though it is plausible they can also achieve such (or close) space complexity.