publication . Conference object . Preprint . Article . 2016

Rate-distance tradeoff for codes above graph capacity

Cullina, Daniel; Dalai, Marco; Polyanskiy, Yury;
Open Access
  • Published: 01 Jul 2016
  • Publisher: IEEE
  • Country: United States
Abstract
National Science Foundation (U.S.) (Grant CCF-13-18620)
Subjects
free text keywords: Geometric graph theory, Graph power, Butterfly graph, Strength of a graph, Line graph, law.invention, law, Voltage graph, Combinatorics, Distance-regular graph, Mathematics, Discrete mathematics, Complement graph, Computer Science - Information Theory
Funded by
NSF| Emerging Frontiers of Science of Information
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0939370
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

[1] M. Dalai, “Elias Bound for General Distances and Stable Sets in EdgeWeighted Graphs,” IEEE Trans. Inform. Theory, vol. 61, no. 5, pp. 2335- 2350, May 2015.

[2] C. E. Shannon, “The Zero-Error Capacity of a Noisy Channel,” IRE Trans. Inform. Theory, vol. IT-2, pp. 8-19, 1956. [OpenAIRE]

[3] L. Lova´sz, “On the Shannon Capacity of a Graph,” IEEE Trans. Inform. Theory, vol. 25, no. 1, pp. 1-7, 1979.

[4] M. Aaltonen, “A new upper bound on nonbinary block codes,” Discrete Mathematics, vol. 83, no. 2, pp. 139-160, 1990. [OpenAIRE]

[5] M. A. Tsfasman, S. Vla˘dut, and T. Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound,” Mathematische Nachrichten, vol. 109, no. 1, pp. 21-28, 1982. [OpenAIRE]

[6] D. B. West, Introduction to graph theory. Prentice Hall Upper Saddle River, 2001, vol. 2.

[7] N. Alon and J. H. Spencer, “Tura´n's theorem,” in The probabilistic method. John Wiley & Sons, 2004, pp. 95-96.

[8] A. Schrijver, “A comparison of the Delsarte and Lova´sz bounds,” IEEE Trans. on Inform. Theory, vol. 25, no. 4, pp. 425 - 429, jul 1979.

[9] M. Navon and A. Samorodnitsky, “On Delsarte's linear programming bounds for binary codes,” in Proc. 46th Annual IEEE Symp.Found. Comp. Sci. (FOCS). IEEE Computer Society, 2005, pp. 327-338. [OpenAIRE]

[10] R. McEliece, E. Rodemich, H. Rumsey, and L. Welch, “New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities,” Information Theory, IEEE Transactions on, vol. 23, no. 2, pp. 157 - 166, mar 1977. [OpenAIRE]

[11] M. E. H. Ismail and P. Simeonov, “Strong Asymptotics for Krawtchouk Polynomials,” J. Comput. Appl. Math., vol. 100, no. 2, pp. 121-144, 1998. [OpenAIRE]

[12] M. O. Albertson and K. L. Collins, “Homomorphisms of 3-chromatic graphs,” Discr. Math., vol. 54, no. 2, pp. 127-132, 1985.

[13] C. Godsil and G. F. Royle, Fractional Chromatic Number. Springer Science & Business Media, 2013, vol. 207.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Conference object . Preprint . Article . 2016

Rate-distance tradeoff for codes above graph capacity

Cullina, Daniel; Dalai, Marco; Polyanskiy, Yury;