@article {654021,
	title = {Deterministic extractors for small-space sources},
	journal = {Journal of Computer and System Sciences},
	volume = {77},
	number = {1},
	year = {2011},
	pages = {191-220},
	abstract = {
	Version History:\&nbsp;Special issue to celebrate Richard Karp{\textquoteright}s Kyoto Prize. Extended abstract in\&nbsp;STOC {\textquoteright}06.



	We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space \(s\) sources on\(\{0,1\}^n\) as sources generated by width \(2^s\) branching programs. Specifically, there is a constant \(η \&gt; 0\) such that for any \(ζ \&gt; n^{-η}\), our algorithm extracts \(m = (δ - ζ)n\) bits that are exponentially close to uniform (in variation distance) from space \(s\) sources with min-entropy \(δn\), where \(s = Ω(ζ^ 3n)\). Previously, nothing was known for \(δ \ll 1/2,\), even for space \(0\). Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of \(r\) independent smaller sources over \(\{0, 1\}^\ell\), where the total min-entropy over all the smaller sources is \(k\). We give deterministic extractors for such sources when \(k\) is as small as \(\mathrm{polylog}(r)\), for small enough \(\ell\).



	\&nbsp;

},
	url = {https://www.sciencedirect.com/science/article/pii/S002200001000098X?via\%3Dihub},
	author = {Jesse Kamp and Anup Rao and Salil Vadhan and David Zuckerman}
}
