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 give versions of Shannon's coding theorem where the decoder runs in constant time:
- Let $D=(D_1,D_2,\ldots,D_n)$ be a product distribution where the $D_i$ have constant support and have dyadic probability masses (i.e., of the form $a/2^b$ where $a,b$ are integers). Then $D$ can be sampled in constant time in ... more >>>
Consider a function that is mildly hard for size-$s$ circuits. For sufficiently large $s$, Impagliazzo's hardcore lemma guarantees a constant-density subset of inputs on which the same function is extremely hard for circuits of size $s'<\!\!<s$. Blanc, Hayderi, Koch, and Tan [FOCS 2024] recently showed that the degradation from $s$ ... more >>>
Zero-knowledge proofs allow to encode a computation so that it can be verified without revealing any additional information beyond its correctness. In this work we focus on proofs that are statistically sound meaning that even an unbounded prover cannot make the verifier accept a false statement, except with negligible probability, ... more >>>
