Revisiting Banaszczyk's 5K-theorem

Speaker(s)

Maud Szusterman

Affiliation

Uniwersytet Warszawski

Language of the talk

English

Date

March 27, 2025, 12:15 p.m.

Room

room 3160

Title in Polish

Revisiting Banaszczyk's 5K-theorem

Seminar

Seminar of Probability Group

---

Banaszczyk's 5K-theorem is an important result in combinatorics. It states that in any dimension n, given any finite sequences of vectors u_1, ... , u_t taken from the unit ball B_2^n , and given any convex body K in R^n, of gaussian measure at least 1/2, the set { ± u_1 ± u_2 ± (...) ± u_t } must intersect with 5K (i.e. there exists a sequence of signs e_i=±1 such that the signed sum \sum_{i≤t} e_i u_i lies in 5K). The problem regained popularity in recent years, due notably to work by Bansal et al. who found an efficient algorithm producing such a sequence of signs; they also derived a generalization where \{ ± u_i \} are replaced by some finite sets F_i (also contained in B_2^n), and obtain that F_1 + ... +F_t must intersect 100 K. We revisit the original paper by Banaszczyk, and provide a simplified proof of the technical part, namely monotonicity of gaussian measure of convex bodies with respect to a certain transform, which we call the Banaszczyk transform. This is a geometric approach. If time permits, we will also explain the limits of this method regarding the generalized statement (the 100K-theorem).

---