English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Randomness extractors, which extract high quality (almost-uniform) randombits from biased random sources, are important objects both in theory and inpractice. While there have been significant progress in obtaining near optimalconstructions of randomness extractors in various settings, the computationalcomplexity of randomness extractors is still much less studied. In particular,it is not clear whether randomness extractors with good parameters can becomputed in several interesting complexity classes that are much weaker than P.  In this paper we study randomness extractors in the following two models ofcomputation: (1) constant-depth circuits (AC0), and (2) the local computationmodel. Previous work in these models, such as [Vio05a], [GVW15] and [BG13],only achieve constructions with weak parameters. In this work we give explicitconstructions of randomness extractors with much better parameters. As anapplication, 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 pseudorandomgenerators for space bounded computation with very good parameters.  Our constructions combine several previous techniques in randomnessextractors, as well as introduce new techniques to reduce or preserve thecomplexity of extractors, which may be of independent interest. These include(1) a general way to reduce the error of strong seeded extractors whilepreserving the AC0 property and small locality, and (2) a seeded randomnesscondenser with small locality.

Randomness Extraction in AC0 and with Small Locality