Topics in Theoretical Computer Science

	Credits	6
	Lecturer	Ola Svensson
	Office hours	TBD
	Schedule	Fridays 13:00-17:00 in INM11

Short description

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced algorithmic techniques, and develop an understanding of fundamental questions that underlie some of the key problems of modern computer science.

This year's course will explore the power of randomness in algorithm design, highlighting how probabilistic techniques can lead to elegant and efficient solutions to a wide range of computational problems. We will cover both foundational methods and advanced applications, with topics drawn from graph algorithms, data structures, learning, and more. The goal is to introduce core probabilistic tools through concrete algorithmic applications. Topics may include: algorithms for finding min-cuts (including isolating cuts and near-linear time methods), graph sparsification (e.g., Karger's and Benczur-Karger techniques), balls-and-bins processes and the power of two choices, low-distortion embeddings and dimension reduction, randomized rounding and discrepancy minimization, fast randomized algorithms for approximate counting via Markov chains, learning from samples, differential privacy, and randomized methods in geometry and communication complexity. We will also discuss fundamental tools such as the Chernoff bound, the Lovasz Local Lemma, martingale inequalities, limited independence, and coupling methods. Selected topics such as online learning, bandits, planted and semi-random models, and randomized primality testing may be included depending on time and interest.

We are running this course in collaboration and in parallel with the Randomized Algorithms course at NYU, taught by Anupam Gupta.

Recommended background: Familiarity with basic algorithms and probability theory.

For previous editions of the course (covering different topics), see e.g., 2014, 2015, 2016.

Schedule and references

TBD

Grading

The course evaluation will be based on 4-5 homework sets, and a research project/presentation at the end of the course. Depending on the class size, some of the homeworks may be oral homeworks(!). For some of the problems, we will ask you to work solo, whereas for others we will allow collaboration in small groups. Each person must write their own solutions to submit.

---