Computer Science/Discrete Mathematics Seminar I

A conjecture of Komlós states that the discrepancy of any collection of unit vectors is $O(1)$, i.e., for any matrix A with unit columns, there is a vector x with -1,1 entries such that $|Ax|_\infty = O(1)$. The related Beck-Fiala conjecture states that any set system with maximum degree k has discrepancy $O(k^{1/2})$.

I will describe an $O((log  n)^{1/4})$ bound for the Komlós problem, improving upon an $O((log  n)^{1/2})$ bound due to Banaszczyk.  Time permitting, we will see how these ideas can be used to resolve the Beck-Fiala conjecture for $k >= (log  n)^2$.