Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

Understand

An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of $\ell_2$ norm at most $1/5$ and any convex body $K$ of Gaussian measure $1/2$ in $\mathbb{R}^n$, there exists a signed combination of these vectors which lands inside $K$.

• A major open problem is to devise a constructive version of Banaszczyk's vector balancing theorem, i.e.
• to find an efficient algorithm which constructs the signed combination.
• We make progress towards this goal along several fronts.