A subspace-evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>>

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the ... more >>>