Randomness is at core of many areas of computer science, from complexity theory and design of efficient algorithms to distributed computing and machine learning. In this course we learn the basics of probabilistic analysis by studying two closely related topics: randomised algorithms and probabilistic method.
Use of a “coin flip” to make decisions makes it possible for algorithms to avoid worst-case scenarios. Consequently, if one is willing to accept a small probability of an error, such randomised algorithms are often faster, simpler, or simply more elegant than deterministic ones. Examples include Welzl’s algorithm for finding a smallest enclosing ball, Karger’s min-cut algorithm, Luby’s algorithm for maximal independent set in a distributed setting, and colour-coding paradigm for finding long paths.
Rather than being solely a concept of study of probability theory, randomness has also become a core tool in many other areas of mathematics. Use of “coin flips” to construct graphs with complex properties or to unveil patterns constitutes a technique known as the probabilistic method. We cover examples such as constructions of graphs with large girth and large chromatic number, and constructions of the so-called expander graphs, one of the central objects in theoretical computer science.
We aim to cover a range of tools and techniques used in probabilistic analysis through study of randomised algorithms, applications of linearity of expectation in analysis of randomised algorithms and probabilistic method, basic concentration inequalities such as Markov’s, Chebyshev’s, and Chernoff’s inequality, as well as more advanced ones such as inequalities of Azuma and Talagrand, analysis of hashing through balls-into-bins problem, compression argument used in analysis of Moser’s LLL algorithm, random walks on graphs and Markov chains, combinatorial properties of random structures and probabilistic construction of expanders, applications of expanders in theoretical computer science, and so on.
This is a fast paced theoretical course with no programming assignments! The emphasis is on mathematically rigorous analysis and proofs. Previous experience in probability and discrete mathematics is necessary. Experience in design of algorithms is recommended.
To help you decide whether this course would be interesting for you, consider the following two problems:
1. Design efficient (randomised) algorithm which finds a path of length log(n) in a graph G.
2. Construct a graph with n vertices such that there is no subset of vertices of size log(n)/2 with the following property: either all vertices are connected by an edge, or none is.
In both problems, flipping a coin is crucial! Don’t worry if you do not manage to solve them – these are difficult problems with surprisingly elegant solutions that we cover in the first week.