Balancing Vectors in Any Norm

In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside β K. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. ~Math '81), Spencer's "six standard deviations suffice" theorem (Trans. ~Amer. ~Math. ~Soc '85) and Banaszczyk's vector balancing theorem (Random Structures & Algorithms '98) correspond to bounds on vector balancing constants. The above theorems have inspired much research in recent years within theoretical computer science. In this work, we show that all vector balancing constants admit "good" approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Our proof is algorithmic, and we show that Rothvoss's (FOCS '14) partial coloring algorithm can be analyzed to obtain these guarantees. Second, we present a novel convex program which encodes the "best possible way" to apply Banaszczyk's vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^2. 5 n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm.

Authors

• Daniel Dadush
• Aleksandar Nikolov
• Kunal Talwar
• Nicole Tomczak-Jaegermann

Keywords

• Approximation algorithms
• Additives
• Computer science
• Tools
• Atmospheric measurements
• Particle measurements
• Complexity theory
• Estimation Algorithm
• Convex Optimization
• Theoretical Computer Science
• Lower Bound
• Objective Function
• Upper Bound
• Conjecture
• Dimensional Space
• Ellipsoid
• Random Walk
• Normal Operation
• Natural Question
• Linear Operator
• Incidence Matrix
• Dual Space
• Normed Space
• Dual Form
• General Norms
• Error Profiles
• Gaussian Measurement
• Lagrange Duality
• Polylogarithmic
• Discrepancy
• Convex Geometry
• Gaussian measure
• M-ellipsoid
• K-convexity