In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 >>>
