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 >>>