Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Chattopadhyay, Eshan; Hatami, Pooya; Hosseini, Kaave; Lovett, Shachar http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88880
URL:

; ; ;

Pseudorandom Generators from Polarizing Random Walks

pdf-format:


Abstract

We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1,1]^n. Next, we use a fractional pseudorandom generator as steps of a random walk in [-1,1]^n that converges to {-1,1}^n. We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2018:8888,
  author =	{Eshan Chattopadhyay and Pooya Hatami and Kaave Hosseini and Shachar Lovett},
  title =	{{Pseudorandom Generators from Polarizing Random Walks}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8888},
  URN =		{urn:nbn:de:0030-drops-88880},
  doi =		{10.4230/LIPIcs.CCC.2018.1},
  annote =	{Keywords: AC0, branching program, polarization, pseudorandom generators, random walks, Sensitivity}
}

Keywords: AC0, branching program, polarization, pseudorandom generators, random walks, Sensitivity
Seminar: 33rd Computational Complexity Conference (CCC 2018)
Issue date: 2018
Date of publication: 2018


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