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 (for example, because it gives a more efficient algorithm, or because the solution is becomes more resilient against and adversary, or simply because it gives a simple and elegant solution to an apparently complicated problem).

Some of the topics seen in the course are the following:
* Randomized algorithms
* Can we really use perfect randomness in computer science?
* Allocation process like balls into bins and random data structures via hash functions
* Branching processes and spread of infections
* Probabilistic method and its application to combinatorics and some games
* Concentration of random variables and martingales, and their applications to routing and dimension reduction
* 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