Bounded Independence versus Symmetric Tests

For a test T ⊆ l0, 1rn, define ka(T) to be the maximum k such that there exists a k-wise uniform distribution over l0, 1rn whose support is a subset of T. For Ht e lx ∈ l0, 1rn : v ∑ixi − n/2v ≤ tr, we prove ka(Ht) e Θ (t2/n + 1). For Sm, c e lx ∈ l0, 1rn : ∑ixi ≡ c (mod m)r, we prove that ka(Sm, c) e Θ (n/m2). For some k e O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over Sm, c. Finally, for any fixed odd m we show that there is an integer k e (1 − Ω(1))n such that any k-wise uniform distribution lands in T with probability exponentially close to vSm, cv/2n; and this result is false for any even m.