TY - GEN
T1 - Rate-distance tradeoff for codes above graph capacity
AU - Cullina, Daniel
AU - Dalai, Marco
AU - Polyanskiy, Yury
N1 - Funding Information:
The research was supported by the NSF grant CCF-13-18620 and NSF Center for Science of Information (CSoI) under grant agreement CCF-09-39370. The work was partially done while visiting the Simons Institute for the Theory of Computing at UC Berkeley, whose support is gratefully acknowledged
Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - 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 where edges in the power graphs are removed between sequences which differ in more than a fraction δ of coordinates. The proposed generalization can be interpreted as the problem of determining the highest rate of zero undetected-error communication over a link with adversarial noise, where only a fraction δ of symbols can be perturbed and only some substitutions are allowed. We derive lower bounds on achievable rates by combining graph homomorphisms with a graph-theoretic generalization of the Gilbert-Varshamov bound. We then give an upper bound, based on Delsarte's linear programming approach, which combines Lovász' theta function with the construction used by McEliece et al. for bounding the minimum distance of codes in Hamming spaces.
AB - 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 where edges in the power graphs are removed between sequences which differ in more than a fraction δ of coordinates. The proposed generalization can be interpreted as the problem of determining the highest rate of zero undetected-error communication over a link with adversarial noise, where only a fraction δ of symbols can be perturbed and only some substitutions are allowed. We derive lower bounds on achievable rates by combining graph homomorphisms with a graph-theoretic generalization of the Gilbert-Varshamov bound. We then give an upper bound, based on Delsarte's linear programming approach, which combines Lovász' theta function with the construction used by McEliece et al. for bounding the minimum distance of codes in Hamming spaces.
UR - http://www.scopus.com/inward/record.url?scp=84985898319&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84985898319&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2016.7541515
DO - 10.1109/ISIT.2016.7541515
M3 - Conference contribution
AN - SCOPUS:84985898319
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1331
EP - 1335
BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016
Y2 - 10 July 2016 through 15 July 2016
ER -