English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Given vectors $\mathbb{v}_1, \ldots, \mathbb{v}_n \in \mathbb{R}^d$ withEuclidean norm at most $1$ and $\mathbb{x}_0 \in [-1,1]^n$, our goal is tosample a random signing $\mathbb{x} \in \{\pm 1\}^n$ with$\mathbb{E}[\mathbb{x}] = \mathbb{x}_0$ such that the operator norm of thecovariance 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 algorithmicdiscrepancy 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 showit is NP-hard to distinguish a list of vectors for which there exists a randomsigning with expectation ${\bf 0}$ such that the operator norm is $0$ fromthose for which any signing with expectation ${\bf 0}$ must have the operatornorm $\Omega(1)$. Second, we consider $\mathbb{x}_0 \in [-1,1]^n$ whose entriesare all around an arbitrarily fixed $p \in [-1,1]$. We show it is NP-hard todistinguish a list of vectors for which there exists a random signing withexpectation $\mathbb{x}_0$ such that the operator norm is $0$ from those forwhich any signing with expectation ${\bf 0}$ must have the operator norm$\Omega((1-|p|)^2)$.

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