A critical notion in coding theory is that of a
good code—a code with constant rate and distance. A natural analogous notion in the p-norm (1 <= p <= 2) is that of a
good l_p-spread subspace. A linear subspace C \subset R^n is called
good l_p-spread if dim(C) >= Omega(n) "constant rate"), and every x \in C \ {0} is at least Omega(|x|_p)-far (in l_p-distance) from any O(n)-sparse vector. The p=2 case, in which C is called a
Euclidean Section, is of particular importance.
In this talk we focus on
sparse l_p-spread matrices, namely, sparse matrices whose kernel is a good l_p-spread subspace. Such a matrix is analogous to the parity-check matrix of an
LDPC code. We also study the stronger notion of a
sparse (Omega(n), O(1))-RIP (restricted isometry property) matrix, which we consider as an analogue to an
LTC (Locally testable code).
In this regime, we analyze the l_p-spread and l_p-RIP for random sparse matrices. We prove that sparse l_p-RIP matrices exist for all 1 <= p < 2, but do not exist for p=2. We also explicitly construct l_p-RIP matrices for 1<= p <= p_0, where p_0 > 1 is a universal constant.
Based on joint works with Venkat Guruswami and Peter Manohar.
