Agrawal, Rohit
Samplers and Extractors for Unbounded Functions
Abstract
Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions f from {0,1}^m to the real numbers such that f(U_m) has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best known constructions of averaging samplers for [0,1]bounded functions in the regime of parameters where the approximation error epsilon and failure probability delta are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman's equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the KullbackLeibler (KL) divergence, are of independent interest. In particular, KLextractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and nonconstructively) as standard extractors.
BibTeX  Entry
@InProceedings{agrawal:LIPIcs:2019:11274,
author = {Rohit Agrawal},
title = {{Samplers and Extractors for Unbounded Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {59:159:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11274},
URN = {urn:nbn:de:0030drops112749},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.59},
annote = {Keywords: averaging samplers, subgaussian samplers, randomness extractors, KullbackLeibler divergence}
}
2019
Keywords: 

averaging samplers, subgaussian samplers, randomness extractors, KullbackLeibler divergence 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

2019 