Rate-distance tradeoff for codes above graph capacity

Article, Preprint English OPEN
Cullina, Daniel ; Dalai, Marco ; Polyanskiy, Yury (2016)
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • Related identifiers: doi: 10.1109/ISIT.2016.7541515
  • Subject: Computer Science - Information Theory

The capacity of a graph is defined as the rate of exponential growth of independent sets in the strong powers of the graph. In the strong power an edge connects two sequences if at each position their letters are equal or adjacent. We consider a variation of the problem... View more
  • References (13)
    13 references, page 1 of 2

    [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.

    [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.

    [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.

    [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.

    [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.

  • Metrics
    No metrics available
Share - Bookmark