8

There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\...


5

For arbitrary $b$, Alon, Babai and Itai showed a lower bound on the probability space size of $m(n,\lfloor k/2 \rfloor)$ where $$ m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$$ which is $\Omega(n^{k/2})$ for constant $k$. They also gave a construction of size $O(n^{k/2})$ in the case of $b = 1$. For $b=1$ there is a paper by Karloff and Mansour which shows ...


3

I have figured out that the answer to this question is yes. The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)


Only top voted, non community-wiki answers of a minimum length are eligible