2026-09-10T09:44:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27765 2026-09-09T12:19:37Z ddc:004 open_access

An Elementary Proof of the First LP Bound on the Rate of Binary Codes Linial, Nati Loyfer, Elyassaf Coding theory code bounds convex optimization linear progamming The asymptotic rate vs. distance problem is a long-standing fundamental problem in coding theory. The best upper bound to date was given in 1977, and has since received numerous proofs and interpretations. Here we provide a new, elementary proof of this bound that is based on counting walks in the Hamming cube. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nati Linial and Elyassaf Loyfer 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.48 urn:nbn:de:0030-drops-277656 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.48 eng https://creativecommons.org/licenses/by/4.0/legalcode