2023/08/30 by Alex Samorodnitsky, Samorodnitsky, Alex
Computer Science · Engineering · #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Optimization and Search Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2308.16038
openalex publication_date 2023/08/30 · openalex created_date 2023/09/02 · openalex updated_date 2026/07/28
The first linear programming bound of McEliece, Rodemich, Rumsey, and Welch is the best known asymptotic upper bound for binary codes, for a certain subrange of distances. Starting from the work of Friedman and Tillich, there are, by now, some arguably easier and more direct arguments for this bound. We show that this more recent line of argument runs into certain difficulties if one tries to go beyond this bound (say, towards the second linear programming bound of McEliece, Rodemich, Rumsey, and Welch).