Paper Info
Title
Randomness Extraction in AC0 and with Small Locality.
Abstract
Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than P. In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits (AC0), and (2) the local computation model. Previous work in these models, such as [Viola 2005 Complexity], [Goldreich 2015 Randomness] and [Bogdanov 2013 Sparse], only achieve constructions with weak parameters. this work we give explicit constructions of randomness extractors with much better parameters. As an application, we use our AC0 extractors to study pseudorandom generators in AC0, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters. Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the AC0 property and small locality, and (2) a seeded randomness condenser with small locality.
Year
Venue
DocType
2016
international workshop and international workshop on approximation, randomization, and combinatorial optimization. algorithms and techniques
Journal
Citations 
PageRank 
References 
1
0.35
10
Authors
2
Name
Order
Citations
PageRank
Kuan Cheng174.86
Xin Li2749118.91