Chernoff type bounds for sums of dependent
random variables and their applications

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.