# 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 I met once a similar notion to what you want in one paper by Mark Zhandry's paper under the name$k$-wise equivalent. I cannot find further references or pointers from that paper, but I think this name nicely describes your something. Concretely, the original definition in the paper is about the distributions over the functions$f: X\rightarrow Y$, and ... 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 Let$m = 1 + \log \ell$. Identify a hash function$h \colon \{0, 1\}^k \to \{0, 1\}^m$with its$n$-bit truth table$h \in \{0, 1\}^n$where$n = m \cdot 2^k$. Our hash family$\mathcal{H} \subseteq \{0, 1\}^n$consists of an$\varepsilon$-biased set for a suitable$\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with ... 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\$ ...