Hardness Results for Minimizing the Covariance of Randomly Signed Sum of Vectors

Given vectors ${\mathbb{v}}_1,\dots ,{\mathbb{v}}_n\in {\mathbb{R}}^d$ with Euclidean norm at most $1$ and ${\mathbb{x}}_0\in [-1,1{]}^n$, our goal is to sample a random signing $\mathbb{x}\in \{\pm 1{\}}^n$ with $\mathbb{E}[\mathbb{x}]={\mathbb{x}}_0$ such that the operator norm of the covariance of the signed sum of the vectors ${\sum }_{i=1}^n\mathbb{x}(i){\mathbb{v}}_i$ is as small as possible. This problem arises from the algorithmic discrepancy theory and its application in the design of randomized experiments. It is known that one can sample a random signing with expectation ${\mathbb{x}}_0$ and the covariance operator norm at most $1$. In this paper, we prove two hardness results for this problem. First, we show it is NP-hard to distinguish a list of vectors for which there exists a random signing with expectation $\mathbf{0}$ such that the operator norm is $0$ from those for which any signing with expectation $\mathbf{0}$ must have the operator norm $\mathrm{\Omega }(1)$. Second, we consider ${\mathbb{x}}_0\in [-1,1{]}^n$ whose entries are all around an arbitrarily fixed $p\in [-1,1]$. We show it is NP-hard to distinguish a list of vectors for which there exists a random signing with expectation ${\mathbb{x}}_0$ such that the operator norm is $0$ from those for which any signing with expectation $\mathbf{0}$ must have the operator norm $\mathrm{\Omega }((1-\mathrm{\mid }p\mathrm{\mid }{)}^2)$.