A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>

We study the one-way number-on-the-forhead (NOF) communication
complexity of the k-layer pointer jumping problem. Strong lower
bounds for this problem would have important implications in circuit
complexity. All of our results apply to myopic protocols (where
players see only one layer ahead, but can still ... more >>>

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>