Texto completo
| |
| Autor(es): |
Domingos Dellamonica Junior
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2007-03-27 |
| Membros da banca: |
Yoshiharu Kohayakawa;
Marcos Abraham Kiwi Krauskopf;
Arnaldo Mandel
|
| Orientador: | Yoshiharu Kohayakawa |
| Resumo | |
Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\". (AU) | |
| Processo FAPESP: | 04/11501-1 - Pseudoaleatoriedade em combinatoria e em teoria da computacao. |
| Beneficiário: | Domingos Dellamonica Junior |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |