LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
On Beck-Fiala and Komlós Conjectures
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

On Beck-Fiala and Komlós Conjectures

68 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Nikhil Bansal, from the University of Michigan, presents this Institute for Advanced Study seminar on discrepancy theory. He opens with the Komlós conjecture, which claims that for any matrix with unit-length columns there exists a plus-or-minus-one vector making the result small in the infinity norm, and the related Beck-Fiala conjecture, which bounds discrepancy for set systems by the square root of their maximum degree. Bansal walks through a new bound of O((log n)^1/4) for the Komlós problem, improving on a longstanding O((log n)^1/2) result due to Banaszczyk, and sketches the argument behind it. Time permitting, he shows how the same techniques resolve the Beck-Fiala conjecture in the regime where the degree is at least (log n) squared. The talk is aimed at a discrete mathematics and theoretical computer science audience already familiar with discrepancy basics, delivered on a whiteboard with technical detail intact.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 8 m
Compared with MathematicsShorter than 57%
Source channelInstitute for Advanced Study (YouTube)