Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chattopadhyay, Eshan; Gaitonde, Jason; Lee, Chin Ho; Lovett, Shachar; Shetty, Abhishek https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-142843
URL:

; ; ; ;

Fractional Pseudorandom Generators from Any Fourier Level

pdf-format:


Abstract

We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the k-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with k. This interpolates previous works, which either require Fourier bounds on all levels [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. As an example, we show that for polynomial error, Fourier bounds on the first O(log n) levels is sufficient to recover the seed length in [Chattopadhyay et al., 2019], which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor’s theorem and bounding the degree-k Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the L₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for 𝔽₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009].

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2021.10,
  author =	{Chattopadhyay, Eshan and Gaitonde, Jason and Lee, Chin Ho and Lovett, Shachar and Shetty, Abhishek},
  title =	{{Fractional Pseudorandom Generators from Any Fourier Level}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14284},
  URN =		{urn:nbn:de:0030-drops-142843},
  doi =		{10.4230/LIPIcs.CCC.2021.10},
  annote =	{Keywords: Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis}
}

Keywords: Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis
Seminar: 36th Computational Complexity Conference (CCC 2021)
Issue date: 2021
Date of publication: 08.07.2021


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