# Tag Info

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 $\... 4 Yes. You can generate a random polynomial of degree$k$, then evaluate this polynomial at$n$different points in$\tilde{O}(n)$time using the DFT (the DFT lets you evaluate a polynomial of degree$n$at$n$different points in$\tilde{O}(n)$time). 3 If you are willing to use cryptographic techniques and rely upon cryptographic assumptions and to accept a computational notion of$k$-wise independence, it's posible that format-preserving encryption (FPE) might be helpful. Let me sketch a few different constructions of this sort. (By "computational notion of$k$-wise independence", I mean that no ... 2 $$s = \Theta( k \cdot ( t + \log n ) )$$ As the question mentions, there is an upper bound of$s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$bits for the seed length. Specifically, sample a random polynomial of degree$<k$over a field of size$2^{\max\{t,\lceil \log_2 n \rceil\}}$, and evaluate it at$n$points. This produces$k$-wise independent field ... 2 You can do it with the isolation lemma. Here are the important details (admittedly hastily written): We'll imagine picking a hash function from$H$as follows: first, pick$w_1^0,\ldots,w_n^0,w_1^1,\ldots,w_n^1$uniformly and independently from integer weights in$[1,4n]$. Then pick a threshold$T$in$[1,4n^2]$also uniformly and independently at random. ... 1 Here's an$\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$lower bound following the discussion here with Yuval, and another one with Ross Berkowitz. I assume for simplicity that the sampling process chooses$k$completely random elements$v_1,\ldots,v_k$of$F_2^n$and outputs their span$V$. A little extra work is needed to bound the probability that the$k\$ ...