Paper Info
Title
Extractors for Three Uneven-Length Sources
Abstract
We construct an efficient 3-source extractor that requires one of the sources to be significantly shorter than the min-entropy of the other two sources. Our extractors work even when the longer, n-bit sources have min-entropy n茂戮驴(1)and the shorter source has min-entropy log10n. Previous constructions for independent sources with min-entropy n茂戮驴required 茂戮驴(1/茂戮驴) sources [Rao06]. Our construction relies on lossless condensers [GUV07] based on Parvaresh-Vardy codes [PV05], as well as on a 2-source extractor for a block source and general source [BRSW06].
Year
DOI
Venue
2008
10.1007/978-3-540-85363-3_44
APPROX-RANDOM
Keywords
Field
DocType
n-bit source,min-entropy n,uneven-length sources,shorter source,parvaresh-vardy code,2-source extractor,general source,block source,3-source extractor,independent source,min-entropy log10n
Computer science,Algorithm,Extractor,Lossless compression
Conference
Volume
ISSN
Citations 
5171
0302-9743
4
PageRank 
References 
Authors
0.40
23
2
Name
Order
Citations
PageRank
Anup Rao158132.80
David Zucherman22588266.65