Extração de aleatoriedade a partir de fontes defeituosas

• Ano de defesa: 2007
• Autor(a) principal: Dellamonica Junior, Domingos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: additive number theory; aleatoriedade; algorithms; algoritmos; combinatória; combinatorics; complexidade computacional; computational complexity; desaleatorização; dispersers; extractors; pseudoaleatoriedade; pseudorandomness; randomness; teoria aditiva dos números
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-160412/

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\".