Description
Vector balancing problems have been studied extensively for at least half a century, while their siblings, anti-balancing problems received much less attention. In this talk, we make up for this deficit by considering the following problem. Given a norm on R^d, and a positive integer n, what is the largest constant C(n) so that for any set of n unit vectors in the chosen norm, one can assign signs to them for which the signed sum has norm at least C(n)? Equivalently, one would like to partition the set of vectors into two parts so that the corresponding sums are far from each other in the specified norm. We show that the worst case (i.e. the smallest C(n)) corresponds to the maximum norm, while C(n) is asymptotically the largest for the Euclidean norm. En route, we also introduce the notion of the polarization constant of general convex bodies, demonstrate its connection to the question of large signed sums, and in the limit case, to the 1-absolutely summing and projection constants. We will also discuss connections to vector retrieval problems.
This is joint work with Florian Grundbacher (TU Munich).