Yoshiharu Kohayakawa
IME-USP
Sexta-feira, 18 de outubro de 2002, 14:30
Sala 268, Bloco A, IME-USP
Resumo:
Após uma discussão sobre a noção de grafos pseudo-aleatórios e sua relevância em combinatória e em teoria da computação, discutiremos medidas de pseudo-aleatoriedade para seqüências binárias. Apresentaremos (a) um resultado conjunto com V. Rödl que dá uma caracterização espectral para seqüências esparsas pseudo-aleatórias e (b) resultados conjuntos com C. Mauduit, C. Moreira, e V. Rödl sobre o valor de certas medidas de pseudo-aleatoriedade para seqüências binárias aleatórias.