Università Roma Tre

The goal of the course is to discuss modern methods from probability theory and their use to solve fundamental problems from other areas, such as computer science (randomized algorithms and random networks), combinatorics and data science. In particular, in the course we see several applications where the problem to be solved is in fact *not random*, but we choose to resort to a probabilistic solution in an opportunistic way to solve them.

Some of the topics seen in the course are the following:
* Randomized algorithms
* Can we really use perfect randomness in computer science?
* Probabilistic method and its application to computer science, combinatorics and some games
* Concentration of random variables and martingales, and their applications to routing and dimension reduction
* Branching processes and spread of infections
* Percolation, Erdos-Renyi random graphs and random networks
* Random walks on graphs and application to clustering data

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons