Skip to main content
2 of 2
added 161 characters in body

The answer is, up to a constant factor $\omega(S) = \Theta(\min(\sqrt{d}, rd))$.

To see the upper bound, we can use the fact that if $S \subset Q$, then $\omega(S) \leq \omega(Q)$, therefore $$ \omega(B_2^n \cap r B_\infty^n) \leq \min(\omega(B_2^n), r \omega(B_\infty^n)) = \min( \mathbb{E}_{z \sim \mathcal{N}(0, I)} \|z\|_2, r\, \mathbb{E}_{z \sim \mathcal{N}(0, I)} \|z\|_1) = \mathcal{O}(\min(\sqrt{d}, rd)). $$

For the lower bound, note that for any given vector $z$, we can chose $\tilde{z} \in S$ to be $\tilde{z}_i := \min(1/\sqrt{d}, r) \mathrm{sgn}(z_i)$. With this choice, we have for any fixed $z$ $$\sup_{x \in S} x^T z \geq \tilde{z}^T z = \min(1/\sqrt{d}, r) \sum_i |z_i| = \min(1/\sqrt{d}, r) \|z\|_1,$$ and therefore $\omega(S) \geq \min(1/\sqrt{d}, r) \mathbb{E}_{z\sim\mathcal{N}(0, I)} \|z\|_1 = \Omega(\min(\sqrt{d}, rd)$.

Note that this is not inconsistent with the upper bound given by Proposition 1 in the cited paper --- the hypercube $[-r, r]^d$ has $2^d$ vertices, not $2d$.