Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore advanced mathematical concepts in this Computer Science/Discrete Mathematics Seminar lecture examining two fundamental conjectures in discrepancy theory. Delve into the Komlós conjecture, which proposes that any collection of unit vectors has discrepancy O(1), meaning for any matrix A with unit columns, there exists a vector x with -1,1 entries such that |Ax|∞=O(1). Investigate the related Beck-Fiala conjecture stating that any set system with maximum degree k has discrepancy O(k^(1/2)). Learn about a significant improvement to the Komlós problem with an O((log n)^(1/4)) bound, surpassing the previous O((log n)^(1/2)) bound established by Banaszczyk. Discover how these theoretical advances can be applied to resolve the Beck-Fiala conjecture for cases where k ≥ (log n)^2, representing important progress in understanding discrepancy bounds for combinatorial structures.
