Rate vs. Distance - Milestones and Obstacles Towards Improved Bounds
Elyassaf Loyfer (Hebrew University)
Monday, October 14th 2024, 2-3pm
Abstract:
The rate vs. distance problem is a major open problem of coding theory. Significant progress has stalled since 1977. The best-known upper bound, established by MRRW, is derived from Delsarte’s reformulation of the combinatorial question as a linear program (LP). This breakthrough sparked a line of research into stronger optimization problems. However, the more powerful formulations have remained difficult to analyze, and no improved bounds have been achieved yet. In this talk, I will present new results on the analysis of a recently developed LP hierarchy. I will discuss the techniques employed, current limitations, and possible strategies to deal with these challenges.
Based on joint work with Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, and Nati Linial