2016
Towards a constructive version of Banaszczyk’s vector balancing theorem
Publication
Publication
Presented at the
International Workshop on Randomization and Computation
An important theorem of Banaszczyk (Random Structures & Algorithms ‘98) states that for any
sequence of vectors of `2 norm at most 1/5 and any convex body K of Gaussian measure 1/2
in Rn, 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. As our first contribution, we show an
equivalence between Banaszczyk’s theorem and the existence of O(1)subgaussian distributions
over signed combinations. For the case of symmetric convex bodies, our equivalence implies the
existence of a universal signing algorithm (i.e. independent of the body), which simply samples
from the subgaussian sign distribution and checks to see if the associated combination lands
inside the body. For asymmetric convex bodies, we provide a novel recentering procedure, which
allows us to reduce to the case where the body is symmetric.
As our second main contribution, we show that the above framework can be efficiently implemented
when the vectors have length O(1/
plog n), recovering Banaszczyk’s results under
this stronger assumption. More precisely, we use random walk techniques to produce the required
O(1)subgaussian signing distributions when the vectors have length O(1/
plog n), and
use a stochastic gradient ascent method to implement the recentering procedure for asymmetric
bodies.
Additional Metadata  

, ,  
doi.org/10.4230/LIPIcs.APPROXRANDOM.2016  
International Workshop on Randomization and Computation  
Organisation  Networks and Optimization 
Dadush, D.N, Garg, S, Lovett, S, & Nikolov, A. (2016). Towards a constructive version of Banaszczyk’s vector balancing theorem. doi:10.4230/LIPIcs.APPROXRANDOM.2016
