Talk information

Date: Sunday, March 19, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Elyassaf Loyfer (HUJI)
Title: Towards new bounds in the rate vs. distance problem for linear codes

Abstract:

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.