Sparse extractor families for all the entropy

DOI10.1145/2422436.2422496zbMATH Open1364.94224arXiv1207.6260OpenAlexW2135542306MaRDI QIDQ2986901FDOQ2986901

Authors: Andrej Bogdanov, Siyao Guo 

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families, which are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on a random input chosen from X is statistically close to uniform. For strong extractor families (i.e., functions in the family do not take additional randomness) we give upper and lower bounds on the sparsity that are tight up to a constant factor for a wide range of min-entropies. We then prove that for some min-entropies weak extractor families can achieve better sparsity. We show how this construction can be used towards more efficient parallel transformation of (non-uniform) one-way functions into pseudorandom generators. More generally, sparse extractor families can be used instead of pairwise independence in various randomized or nonuniform settings where preserving locality (i.e., parallelism) is of interest.

Full work available at URL: https://arxiv.org/abs/1207.6260

Recommendations

• How to get more mileage from randomness extractors
• Simple extractors for all min-entropies and a new pseudorandom generator
• Extractors and pseudorandom generators
• Construction of extractors using pseudo-random generators (extended abstract)
• Automata, Languages and Programming

zbMATH Keywords

random matricesrandomness extractionparallel cryptography

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Measures of information, entropy (94A17) Cryptography (94A60)

Cites Work

• A theory of the learnable
• On the power of inductive inference from good examples
• Occam's razor
• Teaching a smarter learner.
• Title not available (Why is that?)
• Derandomizing polynomial identity tests means proving circuit lower bounds
• On specifying Boolean functions by labelled examples
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandom generators for space-bounded computation
• Title not available (Why is that?)
• On the complexity of teaching
• Models of cooperative teaching and learning
• Teachability in computational learning
• A model of interactive teaching
• Learning from different teachers
• Algorithmic Learning Theory
• Title not available (Why is that?)
• On the limits of efficient teachability
• Measuring teachability using variants of the teaching dimension
• Title not available (Why is that?)
• A theory of goal-oriented communication
• Recent Developments in Algorithmic Teaching
• Teaching Randomized Learners

Cited In (1)

• Randomness extraction in \(\mathsf{AC}^0\) and with small locality

This page was built for publication: Sparse extractor families for all the entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986901)