摘要:An important theorem of Banaszczyk (Random Structures & Algorithms 1998)
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 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.