On metric properties of maps between Hamming spaces and related graph homomorphisms

DOI10.1016/j.jcta.2016.08.005zbMath1355.05174arXiv1503.02779OpenAlexW2962692598MaRDI QIDQ507807

Yury Polyanskiy

Publication date: 9 February 2017

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.02779

zbMATH Keywords

graph homomorphismerror-correcting codesprojective geometry over \(\mathbb{F}_2\)Schrijver's \(\theta\)-function

Mathematics Subject Classification ID

Theory of error-correcting codes and error-detecting codes (94B99) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Graph Information Ratio ⋮ Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube ⋮ On Capacity Regions of Discrete Asynchronous Multiple Access Channels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Homomorphisms of 3-chromatic graphs
• Bounds for codes in the case of list decoding of finite volume
• Semidefinite programming in combinatorial optimization
• Graph Homomorphisms for Quantum Players
• Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
• Linear-time encodable and decodable error-correcting codes
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
• A comparison of the Delsarte and Lovász bounds
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• On the Shannon capacity of a graph
• Hypercontractivity of Spherical Averages in Hamming Space
• On a combinatorial conjecture of Erdös
• On the optimum of Delsarte's linear program

This page was built for publication: On metric properties of maps between Hamming spaces and related graph homomorphisms