Questions tagged [limited-independence]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8 votes
1 answer

A bounded-independence variant of the Berry-Esseen theorem

I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is ...
Dean's user avatar
  • 225
9 votes
1 answer

$k$-wise independent probability spaces

I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following: Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of $...
David Harris's user avatar
  • 3,498
4 votes
1 answer

Is being fooled by limited independence preserved by products?

Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\...
Thomas's user avatar
  • 2,803