Venkatesan Guruswami, Swastik Kopparty

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

Venkatesan Guruswami, Carol Wang

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>