Quadro de avisos

============================================================
Seminário de Teoria da Computação e Combinatória
============================================================

Título: O mundo dos expansores

Palestrante: Guilherme Oliveira Mota (UFC)

Data: sexta, 3 de outubro de 2008, 14:00

Local: Anfiteatro do NUMEC

============================================================
Expansores são, de modo informal, grafos que apesar de
esparsos possuem boa conectividade. A existência desses
grafos foi comprovada há trinta e cinco anos, através de
argumentos combinatórios simples, fazendo uso do método
probabilístico. Desde então surgiram algumas construções
determinísticas, dentre as quais podemos citar o famoso
produto Zig-Zag, que juntamente com potências de grafos pode
ser utilizado para gerar expansores.

Esses grafos têm aplicações em diversas áreas de
conhecimento. Em Ciência da Computação, são úteis para a
modelagem de redes de comunicação e podem ser utilizados
para reduzir a necessidade de bits aleatórios em algoritmos
probabilísticos; além de serem úteis em campos como
Matemática e Física. Esses são apenas alguns exemplos que
ilustram a importância desses grafos.

Neste seminário, faremos uma viagem pelo mundo dos
expansores, abordando desde sua existência até os problemas
resolvidos com o uso de expansores na atualidade.

Nos seminários de Combinatória Extremal e Métodos
Probabilísticos, no mesmo dia, veremos uma aplicação de
expansores à teoria da complexidade (prova de O. Reingold de
que SL = L).
============================================================