TR16-102 Authors: Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola

Publication: 4th July 2016 12:55

Downloads: 444

Keywords:

Let $k=k(n)$ be the largest integer such that there

exists a $k$-wise uniform distribution over $\zo^n$ that

is supported on the set $S_m := \{x \in \zo^n : \sum_i

x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We

show that $\Omega(n/m^2 \log m) \le k \le 2n/m + 2$. For

$k = O(n/m)$ we also show that any $k$-wise uniform

distribution puts probability mass at most $1/m + 1/100$

over $S_m$. Finally, for any fixed odd $m$ we show that

there is $k = (1-\Omega(1))n$ such that any $k$-wise

uniform distribution lands in $S_m$ with probability

exponentially close to $|S_m|/2^n$; and this result is

false for any even $m$.