We prove that the sum of d small-bias generators L : \F^s \to \F^n fools degree-d polynomials in n
variables over a prime field \F, for any fixed
degree d and field \F, including \F = \F_2 = {0,1}.

Our result improves on both the work by Bogdanov and
Viola ... more >>>

We exhibit \epsilon-biased distributions D
on n bits and functions f\colon \{0,1\}^n \to \{0,1\} such that the xor of two independent
copies (D+D) does not fool f, for any of the
following choices:

1. \epsilon = 2^{-\Omega(n)} and f is in P/poly;

2. \epsilon = 2^{-\Omega(n/\log n)} and f is ... more >>>

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over GF(2)= \{0,1\}. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random d-linear ... more >>>

A two-party coin-flipping protocol is \varepsilon-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than \varepsilon. Cleve [STOC '86] showed that r-round o(1/r)-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution Z over \{0,1\}^n, its average bias is: b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|. A source with average bias at most 2^{-k} has min-entropy at least k, and ... more >>>