Skip to Content

Sponsors

No results

Keywords

No results

Types

No results

Search Results

Events

No results
Search events using: keywords, sponsors, locations or event type
When / Where
All occurrences of this event have passed.
This listing is displayed for historical purposes.

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.

Explore Similar Events

  •  Loading Similar Events...

Keywords


Back to Main Content