# Sample integer points of cross-polytope uniformly

For $r,d\in\mathbb{N}$, let

$$C_{r,d}=\{x\in\mathbb{Z}^d: \|x\|_1\le r\}\subset\mathbb{Z}^d$$

be the set of integer points of the $d$-dimensional cross-polytope with radius $r$.

What is (currently) the fastest way to sample from $C_{r,d}$ uniformly? Is there a method which is polynomial in $d$ and $\log(r)$?

• If I understand their paper correctly, then they give an algorithm which is polynomial in $d$ and $\frac{1}{\epsilon}$ to sample from a distribution on $C_{r,d}$ whose distance from the uniform distribution on $C_{r,d}$ is at most $\epsilon$ (in total variance), provided that $r\in\Omega(d\cdot\sqrt{d})$. What about the other cases? For example, $r=1$ or $r\in\mathcal{O}(d)$? Jan 24, 2016 at 11:06
• According to Lemma 1 of their paper, the size of $r$ depends also on $\epsilon$, i.e., $r\ge 8\cdot d\cdot\sqrt{\log{\frac{2^d}{\epsilon}}}$. Does that mean that their method cannot be arbitrarily exact for fixed $r$ and $d$? Jan 25, 2016 at 6:55