License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.43
URN: urn:nbn:de:0030-drops-94477
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9447/
Go to the corresponding LIPIcs Volume Portal

Hoza, William M. ; Klivans, Adam R.

Preserving Randomness for Adaptive Algorithms

pdf-format:
LIPIcs-APPROX-RANDOM-2018-43.pdf (0.6 MB)

Abstract

Suppose Est is a randomized estimation algorithm that uses n random bits and outputs values in R^d. We show how to execute Est on k adaptively chosen inputs using only n + O(k log(d + 1)) random bits instead of the trivial nk (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator [Impagliazzo et al., 1994] with a new scheme for shifting and rounding the outputs of Est. We prove that modifying the outputs of Est is necessary in this setting, and furthermore, our algorithm's randomness complexity is near-optimal in the case d <= O(1). As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least theta of a function F: {0, 1}^n -> {-1, 1} using O(n log n) * poly(1/theta) queries to F and O(n) random bits (independent of theta), improving previous work by Bshouty et al. [Bshouty et al., 2004].

BibTeX - Entry

@InProceedings{hoza_et_al:LIPIcs:2018:9447,
  author =	{William M. Hoza and Adam R. Klivans},
  title =	{{Preserving Randomness for Adaptive Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9447},
  URN =		{urn:nbn:de:0030-drops-94477},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.43},
  annote =	{Keywords: pseudorandomness, adaptivity, estimation}
}

Keywords: pseudorandomness, adaptivity, estimation
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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