Full text
| |
| Author(s): |
Domingos Dellamonica Junior
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Defense date: | 2007-03-27 |
| Examining board members: |
Yoshiharu Kohayakawa;
Marcos Abraham Kiwi Krauskopf;
Arnaldo Mandel
|
| Advisor: | Yoshiharu Kohayakawa |
| Abstract | |
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\". (AU) | |