We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>