Randomness has proven to be a powerful tool in the design and analysis of algorithms. This seminar aims to bring students in the forefront of today research topics, by studying recent research papers in the area of randomness in computation.
Some proposed topics:
- Continuous distributions (Poisson, exponential) and queuing theory.
- Lovasz local lemma.
- Markov chain Monte Carlo method (canonical paths, approximating number of matchings, approximating the permanent).
- The correlation decay method for sampling independent sets.
- Phase transitions in random structures (random SAT, random graphs).
- Hash functions.
- Number theoretic randomised algorithms.
- Sample complexity of machine learning algorithms.
