Theory Seminar: On Continuous Analogues of LDPCs and LTCs

Jonathan Mosheiff (Ben-Gurion university)

Wednesday, 05.07.2023, 12:30

Taub 201

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.