skip to main content


Title: Explicit Construction of Multiple Access Channel Resolvability Codes from Source Resolvability Codes
Award ID(s):
1850227
NSF-PAR ID:
10190360
Author(s) / Creator(s):
;
Date Published:
Journal Name:
2020 IEEE International Symposium on Information Theory (ISIT)
Page Range / eLocation ID:
1576 to 1580
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, vertices in Levenshtein graphs may be strings (i.e., words or sequences of characters in a reference alphabet) of possibly different lengths. We study various properties of these graphs, including a necessary and sufficient condition for their shortest path distance to be identical to the edit distance, and characterize their automorphism group and determining number. We also bound the metric dimension (i.e. minimum resolving set size) of Levenshtein graphs. Regarding the latter, recall that a run is a string composed of identical characters. We construct a resolving set of two-run strings and an algorithm that computes the edit distance between a string of length k and any single-run or two-run string in operations. 
    more » « less