Computer Science/Discrete Mathematics Seminar II

Discrepancy theory provides a powerful approach to improve upon the bounds obtained by a basic application of the probabilistic method. In recent years, several algorithmic approaches have been developed for various classical results in the area. In this talk, I will survey some of these ideas and describe a recent algorithmic approach based on  barrier-based potential functions that recovers several state-of-the-art results in a simple and unified way.

Based on joint work with Aditi Laddha and Santosh Vempala.