Expository notes

  1. An overview of some recent results in average-case circuit complexity
  2. The Lovász Local Lemma and its algorithmic version (in Portuguese)
    An exposition of the Lovász Local lemma, some applications of the lemma in extremal combinatorics, together with a proof of the Moser-Tardos algorithmic version.
  3. An introduction to extremal combinatorics (in Portuguese).
    We introduce the use of the probabilistic method and the polynomial method in extremal combinatorics with the following examples: the crossing number inequality, graphs with large girth and large chromatic number, Turán's theorem, Sperner's theorem, Frankl-Wilson theorem, disproof of Borsuk's conjecture and the chromatic number of the R^n.