Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Continuous Analogues of LDPCs and LTCs
event speaker icon
Jonathan Mosheiff (Ben-Gurion university)
event date icon
Wednesday, 05.07.2023, 12:30
event location icon
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.