Geometric Algorithms for Discrepancy (Bachelors or Masters Project):

Given a set system on N elements, we want to color the elements red or blue so that the maximum difference, over all sets, in the number of red and blue elements is minimized. This quantity is known as the discrepancy of the set system. Recently, there has been remarkable progress on obtaining efficient algorithms for computing the discrepancy. In this project, we will study these algorithms with the goal of determining how low discrepancy colorings of a set system relate to its structure.


Further questions about the project: alantha.newman "at" epfl.ch

Responsible professor: Ola Svensson

Back to Theory@EPFL.