TCS+ Talk

Partial coloring is one of the most widely used methods in combinatorial discrepancy. However, in many cases it leads to sub-optimal bounds as the partial coloring step must be iterated a logarithmic number of times, and the errors can add up arbitrarily. I will describe a recent algorithmic approach that overcomes these limitations and can be used to efficiently find colorings matching the so-called Banaszczyk's bound for many problems.

Based on joint works with Daniel Dadush and Shashwat Garg.