MAC5775 - Métodos Probabilísticos em Combinatória e em Teoria da Computação

2o. Semestre de 2000

Aulas

  1. 21/8/2000 Introdução. Grafos com cintura e número cromático arbitrariamente grandes.
  2. 23/8/2000 Conceitos básicos da teoria de probabilidade. Linearidade da esperança. Desigualdades de Markov e Chebyshev. Aplicação: o teorema de Hardy e Ramanujan sobre o número de divisores primos de um inteiro, a demonstração de Turán.
  3. 28/8/2000 Dois teoremas de Erdös sobre a propriedade B. Discussão dos exercícios 1-10 da lista de exercícios.
  4. 30/8/2000 Independência de variáveis aleatórias. Desigualdades exponenciais para grandes desvios, o caso de soma de variáveis independentes. Exemplo: discrepância de grafos. Discrepância em progressões aritméticas, enunciado dos teoremas de Roth, Beck, e Matousek e Spencer (veja J. Matousek e J. Spencer, Discrepancy in arithmetic progressions, J. Amer. Math. Soc. 9(1996), no. 1, 195--204 [versão eletrônica | versão local (.dvi.gz)]).
  5. 4/9/2000 Prova do teorema de Roth sobre a discrepância mínima em progressões aritméticas em [N]={1,...,N}: Teorema 25A de Beck e Chen, Irregularities of Distributions.
  6. 6/9/2000 Outra aplicação de desigualdades exponenciais para grandes desvios: famílias exponenciais de vetores quase-ortogonais em R^n.
  7. 11/9/2000 Discussão sobre dois problemas de Sidon, incluindo o enunciado do teorema de Ruzsa (veja I. Ruzsa, An infinite Sidon sequence, J. Number Theory 68(1998), no. 1, 63--71 [versão eletrônica]). Discussão informal sobre produtos enumeráveis de espaços de probabilidade finitos (com 2 pontos). O primeiro lema de Borel-Cantelli. Uma ótima referência para este material é o livro Sequences, de Halberstam e Roth.
  8. 13/9/2000 A solução de Erdös para o primeiro problema de Sidon: o teorema de Erdös sobre a existência de bases de ordem 2 tais que todo n é representável O(log n) vezes.
  9. 18/9/2000 A desigualdade FKG e a desigualdade de Janson.
  10. 20/9/2000 Aula de exercícios, sob responsabilidade de Jair Donadelli Jr.
  11. 25/9/2000 A generalização de Erdös e Tetali (bases de ordem k > 2; veja P. Erdös e P. Tetali, Representations of integers as the sum of k terms, Random Structures Algorithms 1(1990), no. 3, 245--261). Comentários sobre uma demonstração de Lovász do teorema de Roth sobre discrepância mínima em progressões aritméticas (infelizmente, não vimos nada sobre isto) [roth.pdf.gz].
  12. 27/9/2000 Variáveis duas-a-duas independentes e funções de hashing 2-universais. Construções; espaços "pequenos". Uma aplicação em derandomization. Notas de Luby e Wigderson [ps.gz]
  13. 2/10/2000 Continuação. Esquemas de hashing (introdução).
  14. 4/10/2000 O esquema de hashing the Fredman, Komlós, e Szemerédi [Storing a sparse table with $O(1)$ worst case access time, J. Assoc. Comput. Mach. 31(1984), no. 3, 538--544 e Storing a sparse table with $O(1)$ worst case access time, 23rd Annual Symposium on Foundations of Computer Science (Chicago, Ill., 1982), 165--169, IEEE, New York, 1982]. Introdução às classes RP e BPP.
  15. 9/10/2000 [Workshop ProNEx em Itatiaia - Algoritmos de Aproximação] Não houve aula
  16. 11/10/2000 [Workshop ProNEx em Itatiaia - Algoritmos de Aproximação] Não houve aula
  17. 16/10/2000 Teorema de Sipser sobre a classe BPP.
  18. 18/10/2000 Continuação do teorema de Sipser. Introdução à amplificação determinística (Seção 9 de Luby e Wigderson [ps.gz]).
  19. 23/10/2000 Geradores de números pseudo-aleatórios: amplificação determinística. Gerador de Chor-Goldreich, gerador de Nisan e o "Hash-Mixing Lemma" de Nisan.
  20. 25/10/2000 Continuação. Grafos expansores e autovalores (Luby-Wigderson, Seção 13) "Expander-Mixing Lemma", Teorema de Lubotzky, Phillips, e Sarnak e Margulis.
  21. 30/10/2000 Não houve aula (?).
  22. 1/11/2000 Funções unidirecionais (LW, Seção 17). Exemplos/conjecturas. O esquema RSA.
  23. 6/11/2000 O "Hard-Core predicate" e o "Hidden Bit Theorem". Espaço do produto interno, "Hidden Bit Technical Lemma".
  24. 8/11/2000 Prova do "Hidden Bit Technical Lemma".
  25. 13/11/2000 [Semana do break] Não houve aula.
  26. 15/11/2000 [Semana do break] Não houve aula.
  27. 20/11/2000 Quase independência k-a-k. Uma construção de Alon, Goldreich, Hastad, e Peralta, baseada resíduos quadráticos. Lema de U. Vazirani, teorema de Weil.
  28. 22/11/2000 Continuação.
  29. 27/11/2000 [Yoshi em Brasilia] Não houve aula.
  30. 29/11/2000 [Yoshi em Brasilia] Não houve aula.
  31. 4/12/2000 Seminário Renato: ordens aleatórias. O resultado de Barak e Erdös sobre a concentração da largura de ordens aleatórias e a lognormalidade do número de extensões lineares (enunciado).
  32. 6/12/2000 Seminário Eduardo: a prova de Gowers do caso k = 4 do teorema de Szemerédi.
  33. 8/12/2000 Continuação.
  34. 11/12/2000 Continuação.
  35. 13/12/2000 Não houve aula.
  36. 18/12/2000 Seminário Elói: provas interativas.
  37. 20/12/2000 Seminário Pavlos: um teorema de Ruzsa.

Calendário

         August 2000             September 2000            October 2000    
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
            1  2  3  4  5                     1  2      1  2  3  4  5  6  7 
      6  7  8  9 10 11 12      3  4  5  6  7  8  9      8  9 10 11 12 13 14 
     13 14 15 16 17 18 19     10 11 12 13 14 15 16     15 16 17 18 19 20 21 
     20 21 22 23 24 25 26     17 18 19 20 21 22 23     22 23 24 25 26 27 28 
     27 28 29 30 31           24 25 26 27 28 29 30     29 30 31 

        November 2000            December 2000        
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa    
               1  2  3  4                     1  2    
      5  6  7  8  9 10 11      3  4  5  6  7  8  9    
     12 13 14 15 16 17 18     10 11 12 13 14 15 16    
     19 20 21 22 23 24 25     17 18 19 20 21 22 23    
     26 27 28 29 30           24 25 26 27 28 29 30    
                              31
Página principal de MAC5775 (2o. Semestre de 2000).
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Sat Dec 16 17:33:59 BRDT 2000