When: Sunday, March 19, 10am
Where: Schreiber 309
Speaker: Elyassaf Loyfer,
Hebrew University
Title:
Towards New Bounds in the Rate vs. Distance Problem for Linear Codes
The rate vs. distance is a fundamental problem in coding theory. It hasn't seen improvement since 1977. The problem is to find the maximum size of a code with a given minimal distance. The best upper bound we have on this quantity uses a linear program by Delsarte. Based on Delsarte's ideas, we develop a family of LPs that yield increasingly tight bounds. Our bounds apply only to linear codes. Numerical results demonstrate the strength of our approach. Parallel work by Coregliano et al. proves that the LP family converges to the quantity we seek. The tightest upper bound is obtained by constructing a dual solution to Delsarte's LP. The first to prove it were McEliece, Rodemich, Ramsey, and Welch (MRRW) in 1977. We adapt their method to our LP family and discuss what are the next steps towards better bounds.
Joint work with Nati Linial.