A Caltech Library Service

Variable-Length Extractors

Zhou, Hongchao and Bruck, Jehoshua (2012) Variable-Length Extractors. In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT). IEEE , Piscataway, NJ, pp. 1107-1111. ISBN 978-1-4673-2580-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study the problem of extracting a prescribed number of random bits by reading the smallest possible number of symbols from non-ideal stochastic processes. The related interval algorithm proposed by Han and Hoshi has asymptotically optimal performance; however, it assumes that the distribution of the input stochastic process is known. The motivation for our work is the fact that, in practice, sources of randomness have inherent correlations and are affected by measurement’s noise. Namely, it is hard to obtain an accurate estimation of the distribution. This challenge was addressed by the concepts of seeded and seedless extractors that can handle general random sources with unknown distributions. However, known seeded and seedless extractors provide extraction efficiencies that are substantially smaller than Shannon’s entropy limit. Our main contribution is the design of extractors that have a variable input length and a fixed output length, are efficient in the consumption of symbols from the source, are capable of generating random bits from general stochastic processes and approach the information theoretic upper bound on efficiency.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2012 IEEE. Date of Current Version: 27 August 2012.
Record Number:CaltechAUTHORS:20120828-165227181
Persistent URL:
Official Citation:Zhou, Hongchao; Bruck, Jehoshua; , "Variable-length extractors," Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on , vol., no., pp.1107-1111, 1-6 July 2012
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:33635
Deposited By: Aucoeur Ngo
Deposited On:29 Aug 2012 20:09
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page