A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, ... more >>>

We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box ... more >>>

We investigate the behavior of the non-negative rank of a matrix, $\hbox{rk}_+$, on Kronecker product, $\times$. Beasley et al. [2013] constructed matrices with $\hbox{rk}_+(M\times M)$ strictly smaller than $\hbox{rk}_+(M)^2$.
We will show that i) there exists an $M$ with $\hbox{rk}_+(M\times M)\leq O(\hbox{rk}_+(M)\log(\hbox{rk}_+(M))$.

Defining asymptotic non-negative rank as $\overline{\hbox{rk}}_+(M):= \lim_{k\rightarrow ... more >>>