## Abstract

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL = L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan [Nis92], pseudorandom generators with seed-length O (log ^{2} n) were constructed (see also [INW94], [GR14]). Unfortunately, improving on this seed-length in general has proven challenging and seems to require new ideas. A recent line of inquiry (e.g., [BV10], [GMR+12], [IMZ12], [RSV13], [SVW14], [HLV17], [LV17], [CHRT17]) has suggested focusing on a particular limitation of the existing PRGs ([Nis92], [INW94], [GR14]), which is that they only fool roBPs when the variables are read in a particular known order, such as x _{1} < · · · < xn. In comparison, existentially one can obtain logarithmic seed-length for fooling the set of polynomialsize roBPs that read the variables under any fixed unknown permutation x _{π(1)} < ··· < x _{π(n)} . While recent works have established novel PRGs in this setting for subclasses of roBPs, there were no known n ^{o(1)} seed-length explicit PRGs for general polynomial-size roBPs in this setting. In this work, we follow the "bounded independence plus noise" paradigm of Haramaty, Lee and Viola [HLV17], [LV17], and give an improved analysis in the general roBP unknown-order setting. With this analysis we obtain an explicit PRG with seed-length O(log ^{3} n) for polynomial-size roBPs reading their bits in an unknown order. Plugging in a recent Fourier tail bound of Chattopadhyay, Hatami, Reingold, and Tal [CHRT17], we can obtain a Õ(log ^{2} n) seed-length when the roBP is of constant width.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |

Editors | Mikkel Thorup |

Publisher | IEEE Computer Society |

Pages | 946-955 |

Number of pages | 10 |

ISBN (Electronic) | 9781538642306 |

DOIs | |

State | Published - Nov 30 2018 |

Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: Oct 7 2018 → Oct 9 2018 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2018-October |

ISSN (Print) | 0272-5428 |

### Other

Other | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
---|---|

Country/Territory | France |

City | Paris |

Period | 10/7/18 → 10/9/18 |

## Keywords

- Fourier analysis
- Pseudorandom generators
- Read-once branching programs
- Unknown order

## ASJC Scopus subject areas

- Computer Science(all)