随机性及随机提取器综述

A Suvey of Randomness and Randomness Extractors

随机提取器是一类可以从任意包含足够随机性的随机分布中提取几乎均匀分布随机位的函数.明确构造的随机提取器在复杂性理论,组合数学和密码学中有很多应用.这一领域有许多最新进展.

Randomness extractors are functions that ＂extract＂ （almost uniformly distributed） random bits from arbitrary distributions that ＂contain＂ sufficient randomness. Explicit constructions of randomness extractors have many applications in complexity theory and combinatorics. This paper is a survey of recent developments in the area.