This repository contains my graded homework solutions for the course CS-455: Topics in Theoretical Computer Science at EPFL, taught jointly with NYU.
The course was given by Prof. Ola Svensson and Prof. Michael Kapralov (EPFL), in collaboration with Prof. Anupam Gupta (NYU).
The course explored the power of randomness in algorithm design, showing how probabilistic techniques can lead to elegant and efficient solutions to complex computational problems. It covered both foundational principles and modern applications, with examples drawn from graph algorithms, data structures, learning theory, and optimization.
Key topics included graph sparsification, randomized rounding, dimension reduction, Chernoff bounds, martingale inequalities, and the Lovász Local Lemma. The course also touched on applications such as approximate counting, differential privacy, learning from samples, and randomized methods in geometry and communication complexity.
The EPFL offering was conducted in collaboration with the Randomized Algorithms course at NYU, running in parallel across both institutions.
The problem statements in these assignments were created by the course instructors and teaching staff.
The solutions presented here were collaboratively written by Zachary Doll and Simon Barras, a fellow EPFL student.
All documents were written and compiled using LaTeX.
- These materials are provided for personal reference and educational purposes only.
- Please respect the academic integrity policies of EPFL and NYU — do not copy or submit these solutions as your own work.
- The repository is meant as a record of my own work and for future self-study.
Authors: Zachary Doll, Simon Barras Institution: École Polytechnique Fédérale de Lausanne (EPFL)