Abstract
We give an explicit construction of a function that is almost a 2-source extractor for linear entropy, it is a condenser where the output has almost full entropy. Given 2 sources with entropy δn, the output of the condenser is a distribution on m-bit strings that is 
-close to having min-entropy 
, where here m is linear in n.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 1–10 (2005)
Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2 source dispersers for n o(1) entropy and Ramsey graphs beating the Frankl-Wilson construction. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006)
Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory 1, 1–32 (2005)
Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis 14, 27–57 (2004)
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing 17(2), 230–261 (1988)
Dvir, Z., Raz, R.: Analyzing linear mergers. Technical Report TR05-25, ECCC: Electronic Colloquium on Computational Complexity (2005)
Gabizon, A., Raz, R., Shaltiel, R.: Deterministic extractors for bit-fixing sources by obtaining an independent seed. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004)
Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from parvaresh-vardy codes. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (2007)
Lu, C.J., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: Optimal up to constant factors. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 602–611 (2003)
Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–52 (1996)
Rao, A.: Extractors for a constant number of polynomially small min-entropy independent sources. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006)
Raz, R.: Extractors with weak random seeds. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 11–20 (2005)
Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. Journal of Computer and System Sciences 33, 75–87 (1986)
Shaltiel, R.: How to get more mileage from randomness extractors. In: Proceedings of the 21th Annual IEEE Conference on Computational Complexity, pp. 49–60 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rao, A. (2008). A 2-Source Almost-Extractor for Linear Entropy. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_43
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)