Randomness extraction from defective sources - Dellamonica Jr., Domingos; Kohayakawa, Yoshiharu (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2008: Anais do XXI Concurso de Teses e Dissertações, 2008)
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”.