Presented By: Probability and Analysis Seminar - Department of Mathematics
Probability and Analysis Seminar: On Beck–Fiala and Komlós Conjectures
Nikhil Bansal (University of Michigan)
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.
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.