Pseudorandom generators for read-once branching programs, in any order

Michael A. Forbes, Zander Kelley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages946-955
Number of pages10
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period10/7/1810/9/18

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Pseudorandom generators for read-once branching programs, in any order'. Together they form a unique fingerprint.

  • Cite this

    Forbes, M. A., & Kelley, Z. (2018). Pseudorandom generators for read-once branching programs, in any order. In M. Thorup (Ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (pp. 946-955). [8555171] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00093