Extração de aleatoriedade a partir de fontes defeituosas / Randomness extraction from weak random sources

AUTOR(ES)

Domingos Dellamonica Junior

DATA DE PUBLICAÇÃO

2007

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

ASSUNTO(S)

aleatoriedade pseudoaleatoriedade additive number theory extractors algorithms dispersers computational complexity combinatorics algoritmos desaleatorização pseudorandomness combinatória complexidade computacional randomness teoria aditiva dos números

Documentos Relacionados

• ALEATORIEDADE EM MODELOS DE ISING
• Extração de conhecimento a partir de redes reurais recorrentes
• Influence of lipid extraction and tegument removal from different protein sources on in vitro digestibility
• Inventory of metal loads from diffuse sources of pollution
• Extração de invertase solúvel a partir de levedura de panificação (Saccharomyces cerevisiae)