The University of Michigan Mathematics Colloquium
Large deviation results play a crucial role in the analysis of randomized algorithms and several other areas in both combinatorics and theoretical computer science. In this talk, we present several new concentration results for sums of dependent random variables or functions with large Lipschitz coefficients. The strenght of these results is indicated by the fact that they can be applied in several situations where standard tools such as Chernoff's or Azuma's inequalites fail. Several applications from various areas will be sketched in order to illustrate the power and convenience of these new bounds.