Randomised Algorithms

Aims:

The aim of this course is to introduce advanced techniques in the design and analysis of algorithms, with a strong focus on randomised algorithms. It covers essential tools and ideas from probability, optimisation, and graph theory, and develops this knowledge through a variety of examples of algorithms and processes. This course will demonstrate that randomness is not only an important design technique which often leads to simpler and more elegant algorithms, but can also be essential in settings where time and space are restricted.

Lectures:

Part I: Classical Randomisation (3 Lectures)

Introduction to Randomised Algorithms. Random variables; expectation and linearity of expectation; indicator variables; Markov's and Chebyshev's inequalities; MAX-CUT example.

Random Binary Search Trees and Randomised Quicksort. Quicksort with random pivots; expectation-based running-time analysis; use of indicator random variables; Random binary search trees; expected depth.

Karger's Min-Cut Algorithm. Graph cuts and minimum cuts; random edge contractions and survival-probability analysis; probability amplification; combinatorial implications.

Part II: Randomised Search and Approximation (3 Lectures)

MAX-3-SAT and the Method of Conditional Expectations. Random assignments; expected approximation guarantees; the 7/8-approximation ratio; derandomisation using the method of conditional expectations; brief introduction to linear programming.

Randomised Rounding. Integer programs as relaxations of linear programs; Vertex Cover and deterministic rounding; Set Cover and randomised rounding; probability amplification.

Random Walks and Randomised 2-SAT. Random walks on graphs and paths; stopping and hitting times; a randomised local-search algorithm for 2-SAT; analysis via hitting times; outlook towards 3-SAT.

Part III: Concentration and Learning under Uncertainty (3 Lectures)

Concentration Inequalities. Markov's and Chebyshev's inequalities; Chernoff bounds; proof via moment-generating functions; Hoeffding's inequality; application to load balancing.

Online Learning with Experts. Online learning with experts; the deterministic Weighted Majority algorithm; regret analysis using potential functions; impact of learning rate and limits of deterministic algorithms; randomised Weighted Majority algorithm.

Multi-Armed Bandits. Stochastic bandits and regret; greedy and ε-greedy algorithms; Upper Confidence Bound (UCB) algorithm; analysis using Chernoff bounds; outlook towards other bandit models.

Part IV: Randomised Geometry and Spectral Methods (3 Lectures)

Dimensionality Reduction via Random Projections. Freivalds' algorithm for randomised matrix verification; analysis using the principle of deferred decisions; random projections and the Johnson-Lindenstrauss lemma; analysis using Chernoff bounds for unbounded random variables.

Spectral Graph Theory. Adjacency matrices and graph Laplacians; eigenvalues and the spectrum of a matrix; the Courant-Fischer characterisation; one-dimensional spectral embeddings; links between the spectrum and graph properties.

Spectral Clustering. Conductance as a refined connectivity measure; Cheeger's inequality; the spectral clustering algorithm in a simplified setting; two detailed examples; outlook towards more general settings.

Objectives:

By the end of the course students should be able to:

• learn how to use randomness in the design of algorithms, in particular, approximation algorithms;
• learn the basics of linear programming, integer programming and randomised rounding;
• apply randomisation to various problems coming from optimisation, machine learning and data science;
• use results from probability theory to analyse the performance of randomised algorithms.

Recommended reading

* Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis., Cambridge University Press, 2nd edition.

* David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011