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.
Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following:
- We show that for every total Boolean function, its exact and approximate sparsity ... more >>>
Modular composition is the problem of computing the coefficient vector of the polynomial $f(g(x)) \bmod h(x)$, given as input the coefficient vectors of univariate polynomials $f$, $g$, and $h$ over an underlying field $\mathbb{F}$. While this problem is known to be solvable in nearly-linear time over finite fields due to ... more >>>
We show that Reed-Solomon codes of dimension $k$ and block length $n$ over any finite field $\mathbb{F}$ can be deterministically list decoded from agreement $\sqrt{(k-1)n}$ in time $\text{poly}(n, \log |\mathbb{F}|)$.
Prior to this work, the list decoding algorithms for Reed-Solomon codes, from the celebrated results of ...
more >>>
