On Beck-Fiala and Komlós Conjectures

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, using the framework of discrete Brownian motion guided by semidefinite programs. Time permitting, I will sketch how these ideas can be used to resolve the Beck-Fiala conjecture for k >=(log n)^2.