License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.28
URN: urn:nbn:de:0030-drops-147217
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14721/
Go to the corresponding LIPIcs Volume Portal

Hoza, William M.

Better Pseudodistributions and Derandomization for Space-Bounded Computation

pdf-format:
LIPIcs-APPROX28.pdf (0.9 MB)

Abstract

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-n length-n read-once branching programs (ROBPs) with error ε and seed length O(log² n + log n ⋅ log(1/ε)) [Nisan, 1992]. Nisan’s generator remains the best explicit PRG known for this important model of computation. However, a recent line of work starting with Braverman, Cohen, and Garg [Braverman et al., 2020; Chattopadhyay and Liao, 2020; Cohen et al., 2021; Pyne and Vadhan, 2021] has shown how to construct weighted pseudorandom generators (WPRGs, aka pseudorandom pseudodistribution generators) with better seed lengths than Nisan’s generator when the error parameter ε is small.
In this work, we present an explicit WPRG for width-n length-n ROBPs with seed length O(log² n + log(1/ε)). Our seed length eliminates log log factors from prior constructions, and our generator completes this line of research in the sense that further improvements would require beating Nisan’s generator in the standard constant-error regime. Our technique is a variation of a recently-discovered reduction that converts moderate-error PRGs into low-error WPRGs [Cohen et al., 2021; Pyne and Vadhan, 2021]. Our version of the reduction uses averaging samplers.
We also point out that as a consequence of the recent work on WPRGs, any randomized space-S decision algorithm can be simulated deterministically in space O (S^{3/2} / √{log S}). This is a slight improvement over Saks and Zhou’s celebrated O(S^{3/2}) bound [Saks and Zhou, 1999]. For this application, our improved WPRG is not necessary.

BibTeX - Entry

@InProceedings{hoza:LIPIcs.APPROX/RANDOM.2021.28,
  author =	{Hoza, William M.},
  title =	{{Better Pseudodistributions and Derandomization for Space-Bounded Computation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{28:1--28:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14721},
  URN =		{urn:nbn:de:0030-drops-147217},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.28},
  annote =	{Keywords: Weighted pseudorandom generator, pseudorandom pseudodistribution, read-once branching program, derandomization, space complexity}
}

Keywords: Weighted pseudorandom generator, pseudorandom pseudodistribution, read-once branching program, derandomization, space complexity
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI