ECCC-Report TR16-102https://eccc.weizmann.ac.il/report/2016/102Comments and Revisions published for TR16-102en-usMon, 04 Jun 2018 20:03:29 +0300
Revision 1
| Bounded Independence versus Symmetric Tests |
Ravi Boppana,
Johan Håstad,
Chin Ho Lee,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2016/102#revision1For a test $T \subseteq \{0,1\}^n$ define $k^*$ to be the maximum $k$ such
that there exists a $k$-wise uniform distribution over $\{0,1\}^n$ whose
support is a subset of $T$.
For $T = \{x \in \{0,1\}^n : \abs{\sum_i x_i - n/2} \le t\}$ we prove $k^* =
\Theta(t^2/n + 1)$.
For $T = \{x \in \{0,1\}^n : \sum_i x_i \equiv c \pmod m\}$ we prove that $k^* =
\Theta(n/m^2 + 1)$. For some $k = O(n/m)$ we also show that any $k$-wise
uniform distribution puts probability mass at most $1/m + 1/100$ over $T$.
Finally, for any fixed odd $m$ we show that there is an integer $k =
(1-\Omega(1))n$ such that any $k$-wise uniform distribution lands in
$T$ with probability exponentially close to $|T|/2^n$; and this
result is false for any even $m$.
Mon, 04 Jun 2018 20:03:29 +0300https://eccc.weizmann.ac.il/report/2016/102#revision1
Paper TR16-102
| Bounded independence vs. moduli |
Ravi Boppana,
Johan Håstad,
Chin Ho Lee,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2016/102Let $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$.Mon, 04 Jul 2016 12:55:20 +0300https://eccc.weizmann.ac.il/report/2016/102