TCS+ talk *this week*: Wednesday, November 19, Haotian Jiang, U Chicago
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, November 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Haotian Jiang (U Chicago)
Title: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
Abstract: The Beck-Fiala Conjecture asserts that any set system of n elements with degree k has combinatorial discrepancy O(\sqrt{k}). A substantial generalization is the Komlós Conjecture, which states that any m by n matrix with columns of unit Euclidean length has discrepancy O(1).
In this talk, we describe an \tilde{O}(log^{1/4} n) bound for the Komlós problem, improving upon the O(log^{1/2} n) bound due to Banaszczyk from 1998. We will also see how these ideas can be used to resolve the Beck-Fiala Conjecture for k \geq \log^2 n, and give a \tilde{O}(k^{1/2} + \log^{1/2} n) bound for smaller k, which improves upon Banaszczyk’s O(k^{1/2} \log^{1/2} n) bound. These results are based on a new technique of “Decoupling via Affine Spectral Independence” in designing rounding algorithms, which might also be useful in other contexts.
This talk is based on joint work with Nikhil Bansal (University of Michigan).
Clement Canonne
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow (Wednesday), starting at 12:50pm ET: https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Monday, November 17, 2025 4:00 PM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk *this week*: Wednesday, November 19, Haotian Jiang, U Chicago
Hello everyone,
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, November 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). The speakers' slides will be made available at https://url.au.m.mimecastprotect.com/s/bobkC4QOPEi9LRy21COfrC4KNiO?domain=sites.google.com after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://url.au.m.mimecastprotect.com/s/9Fg7C5QPXJipqwoPGtOhlCkZ0qO?domain=sites.google.com. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: https://url.au.m.mimecastprotect.com/s/ZEkKC6XQ4Lf0QZE6KImiWC5p7WA?domain=youtube.com.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Haotian Jiang (U Chicago)
Title: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
Abstract: The Beck-Fiala Conjecture asserts that any set system of n elements with degree k has combinatorial discrepancy O(\sqrt{k}). A substantial generalization is the Komlós Conjecture, which states that any m by n matrix with columns of unit Euclidean length has discrepancy O(1).
In this talk, we describe an \tilde{O}(log^{1/4} n) bound for the Komlós problem, improving upon the O(log^{1/2} n) bound due to Banaszczyk from 1998. We will also see how these ideas can be used to resolve the Beck-Fiala Conjecture for k \geq \log^2 n, and give a \tilde{O}(k^{1/2} + \log^{1/2} n) bound for smaller k, which improves upon Banaszczyk’s O(k^{1/2} \log^{1/2} n) bound. These results are based on a new technique of “Decoupling via Affine Spectral Independence” in designing rounding algorithms, which might also be useful in other contexts.
This talk is based on joint work with Nikhil Bansal (University of Michigan).
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://url.au.m.mimecastprotect.com/s/kMQgC71R2NTV3nvXkCNs6Co_e8V?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/spoaC81V0PTPnBl5RcotrCyu6Ai?domain=groups.google.com.