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).


2

You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have $$ \delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\rvert}\tag{1} $$ since the squared $\ell_2$ norm of a distribution over support of size $N$ is at least that of the uniform distribution on $N$ elements, which ...


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 ...


1

recall that $$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$ if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have $$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$ So, observe that whenever $p_\tau(x,y)\neq 0$ we win as $z$ is uniform and the expected value of $f_{p_\tau(x,y)}(z)$ is also $1/2$ which means ...


1

The algorithm below runs in time $O(n\log n)$, but not $O(n)$. On the other hand, it permutes the columns in such a way that there are only $O(\log^2n \cdot\log\log n)$ short segments in the end. Let us at first describe $O(n\log n)$-time algorithm for the case when $n + 1$ is prime. Then we may identify columns $\{1, 2, \ldots, n\}$ with elements of $(\...


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