This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $\delta$ is automatically list-decodable with small ... more >>>

A recent manuscript of OpenAI proves that the exponent of matrix multiplication satisfies $\omega\le9/4$. We give an elementary, self-contained proof of this bound. We follow the ideas of the original manuscript, but implement them differently to obtain explicit algorithms. Specifically, for every $\varepsilon>0$, we give a matrix multiplication algorithm with ... more >>>

One of the central questions in space complexity is whether nondeterministic logspace computations (NL) can be simulated in unambiguous logspace (UL). A stronger notion, reach unambiguity (RUL $\subseteq$ UL $\cap$ coUL), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph ... more >>>