Abstract
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|∞=O(1). The related Beck-Fiala conjecture states that any set system with maximum degree k has discrepancy O(k1/2).I will describe an O((logn)1/4) bound for the Komlós problem, improving upon an O((logn)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 greater than =(logn)2.