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.
Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are $\epsilon$-far from the property being verified, where $\epsilon>0$ is a proximity parameter. In such proof systems, the verifier has oracle access to the ... more >>>
A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up to list decoding capacity in their natural setting of parameters. A curious aspect of this work was that unlike most list decoding ... more >>>
We exhibit an $n$-bit partial function with randomized communication complexity $O(\log n)$ but such that any completion of this function into a total one requires randomized communication complexity $n^{\Omega(1)}$. In particular, this shows an exponential separation between randomized and pseudodeterministic communication protocols. Previously, Gavinsky (2025) showed an analogous separation in ... more >>>
