We prove a lower bound of $\Omega\left(n^{1.5}\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_{n}$ (over every field).

We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_{n}: R^n \rightarrow ... more >>>

Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [ABJ+22], the fundamental problem of estimating the $F_p$ moment to within any constant factor requires $\Omega(n)$ memory. In this model, the internal state of the (randomized) streaming algorithm is visible to ... more >>>

We consider (almost) $k$-wise independent hash functions, whose evaluations on any $k$ inputs are (almost) uniformly random, for very large values of $k$. Such hash functions need to have a large key that grows linearly with $k$. However, it may be possible to evaluate them in sub-linear time by ... more >>>