Randomness Extraction in AC0 and with Small Locality

Kuan Cheng, Xin Li

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 be…