Randomness extraction from defective sources
Resumo
Recently, Barak et al. (2004) constructed explicit deterministic extractors and dispersers (these are polynomial-time computable functions) with much better parameters than what was known before. We introduce the concepts involved in such a construction and mention some of its applications; in particular, we describe how it is possible to obtain much better bounds for the bipartite Ramsey problem (a very hard problem) using the machinery developed in that paper. We also present some original results that improve on these constructions. They are inspired by the work of Anup Rao (2005) and uses the recent breakthrough of Jean Bourgain (2005) in obtaining 2-source extractors that break the “1/2-barrier”.
Referências
Barak, B., Impagliazzo, R., and Wigderson, A. (2004). Extracting randomness using few independent sources. In FOCS, pages 384–393. IEEE Computer Society.
Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., and Wigderson, A. (2005). Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 1–10, New York, NY, USA. ACM Press.
Barak, B., Rao, A., Shaltiel, R., and Wigderson, A. (2006). 2-source dispersers for no(1) entropy and Ramsey graphs beating the Frankl-Wilson construction. In STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, New York, NY, USA. ACM Press.
Bourgain, J. (2005). More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1–32.
Dellamonica Jr., D. (2008). Simpler constant-seed condensers. In E. S. Laber et al., editor, Proceedings of Latin American Symposium on Theoretical Informatics (LATIN 2008), volume 4957, pages 664–675. Springer.
Rao, A. (2005). Extractors for a constant number of polynomial min-entropy independent sources. Electronic Colloquium on Computational Complexity (ECCC), 5(106).
Raz, R. (2004). Extractors with weak random seeds. Electronic Colloquium on Computational Complexity (ECCC), 4(099).
Tao, T. and Vu, V. H. (2006). Additive Combinatorics. Cambridge Studies in Advanced Mathematics.
Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., and Wigderson, A. (2005). Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 1–10, New York, NY, USA. ACM Press.
Barak, B., Rao, A., Shaltiel, R., and Wigderson, A. (2006). 2-source dispersers for no(1) entropy and Ramsey graphs beating the Frankl-Wilson construction. In STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, New York, NY, USA. ACM Press.
Bourgain, J. (2005). More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1–32.
Dellamonica Jr., D. (2008). Simpler constant-seed condensers. In E. S. Laber et al., editor, Proceedings of Latin American Symposium on Theoretical Informatics (LATIN 2008), volume 4957, pages 664–675. Springer.
Rao, A. (2005). Extractors for a constant number of polynomial min-entropy independent sources. Electronic Colloquium on Computational Complexity (ECCC), 5(106).
Raz, R. (2004). Extractors with weak random seeds. Electronic Colloquium on Computational Complexity (ECCC), 4(099).
Tao, T. and Vu, V. H. (2006). Additive Combinatorics. Cambridge Studies in Advanced Mathematics.
Publicado
12/07/2008
Como Citar
DELLAMONICA JR., Domingos; KOHAYAKAWA, Yoshiharu.
Randomness extraction from defective sources. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 21. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 97-101.
ISSN 2763-8820.
