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 construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tilde{\Omega}(k^3)$ of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs ... more >>>
Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an $L$-step random walk on an $n$-vertex directed graph requires $\Omega(n L)$ space, implying that no sublinear-space streaming algorithm exists for general graphs.
We show that sublinear algorithms are ... more >>>
We investigate central questions in complexity theory through the lens of time-bounded Kolmogorov complexity, focusing on $\textit{nondeterministic}$ measures [AKRR03] and their extensions. In more detail, we consider succinct encodings of a string by programs that may be nondeterministic (nK), randomized (rK), or combine both resources – yielding richer notions such ... more >>>
