@INPROCEEDINGS{ref:CDRV21,
  author =	 {Mahdi Cheraghchi and Joseph Downs and Jo\~{a}o Ribeiro
                  and Alexandra Veliche},
  title =	 {Mean-Based Trace Reconstruction over Practically any
                  Replication-Insertion Channel},
  year =	 2021,
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  url_Paper =	 {https://arxiv.org/abs/2102.09490},
  url_Link = {https://ieeexplore.ieee.org/document/9518161},
  doi = {10.1109/ISIT45174.2021.9518161},
  abstract =	 {Mean-based reconstruction is a fundamental, natural
                  approach to worst-case trace reconstruction over
                  channels with synchronization errors.  It is known
                  that $\exp(O(n^{1/3}))$ traces are necessary and
                  sufficient for mean-based worst-case trace
                  reconstruction over the deletion channel, and this
                  result was also extended to certain channels
                  combining deletions and geometric insertions of
                  uniformly random bits.  In this work, we use a
                  simple extension of the original complex-analytic
                  approach to show that these results are examples of
                  a much more general phenomenon: $\exp(O(n^{1/3}))$
                  traces suffice for mean-based worst-case trace
                  reconstruction over any memoryless channel that maps
                  each input bit to an arbitrarily distributed
                  sequence of replications and insertions of random
                  bits, provided the length of this sequence follows a
                  sub-exponential distribution.}
}

{"_id":"We7q7M6XvjXrKiJ2a","bibbaseid":"cheraghchi-downs-ribeiro-veliche-meanbasedtracereconstructionoverpracticallyanyreplicationinsertionchannel-2021","author_short":["Cheraghchi, M.","Downs, J.","Ribeiro, J.","Veliche, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Joseph"],"propositions":[],"lastnames":["Downs"],"suffixes":[]},{"firstnames":["João"],"propositions":[],"lastnames":["Ribeiro"],"suffixes":[]},{"firstnames":["Alexandra"],"propositions":[],"lastnames":["Veliche"],"suffixes":[]}],"title":"Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel","year":"2021","booktitle":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","url_paper":"https://arxiv.org/abs/2102.09490","url_link":"https://ieeexplore.ieee.org/document/9518161","doi":"10.1109/ISIT45174.2021.9518161","abstract":"Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\\exp(O(n^{1/3}))$ traces are necessary and sufficient for mean-based worst-case trace reconstruction over the deletion channel, and this result was also extended to certain channels combining deletions and geometric insertions of uniformly random bits. In this work, we use a simple extension of the original complex-analytic approach to show that these results are examples of a much more general phenomenon: $\\exp(O(n^{1/3}))$ traces suffice for mean-based worst-case trace reconstruction over any memoryless channel that maps each input bit to an arbitrarily distributed sequence of replications and insertions of random bits, provided the length of this sequence follows a sub-exponential distribution.","bibtex":"@INPROCEEDINGS{ref:CDRV21,\n author =\t {Mahdi Cheraghchi and Joseph Downs and Jo\\~{a}o Ribeiro\n and Alexandra Veliche},\n title =\t {Mean-Based Trace Reconstruction over Practically any\n Replication-Insertion Channel},\n year =\t 2021,\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n url_Paper =\t {https://arxiv.org/abs/2102.09490},\n url_Link = {https://ieeexplore.ieee.org/document/9518161},\n doi = {10.1109/ISIT45174.2021.9518161},\n abstract =\t {Mean-based reconstruction is a fundamental, natural\n approach to worst-case trace reconstruction over\n channels with synchronization errors. It is known\n that $\\exp(O(n^{1/3}))$ traces are necessary and\n sufficient for mean-based worst-case trace\n reconstruction over the deletion channel, and this\n result was also extended to certain channels\n combining deletions and geometric insertions of\n uniformly random bits. In this work, we use a\n simple extension of the original complex-analytic\n approach to show that these results are examples of\n a much more general phenomenon: $\\exp(O(n^{1/3}))$\n traces suffice for mean-based worst-case trace\n reconstruction over any memoryless channel that maps\n each input bit to an arbitrarily distributed\n sequence of replications and insertions of random\n bits, provided the length of this sequence follows a\n sub-exponential distribution.}\n}\n\n","author_short":["Cheraghchi, M.","Downs, J.","Ribeiro, J.","Veliche, A."],"key":"ref:CDRV21","id":"ref:CDRV21","bibbaseid":"cheraghchi-downs-ribeiro-veliche-meanbasedtracereconstructionoverpracticallyanyreplicationinsertionchannel-2021","role":"author","urls":{" paper":"https://arxiv.org/abs/2102.09490"," link":"https://ieeexplore.ieee.org/document/9518161"},"metadata":{"authorlinks":{}},"downloads":9},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["mean","based","trace","reconstruction","over","practically","replication","insertion","channel","cheraghchi","downs","ribeiro","veliche"],"title":"Mean-Based Trace Reconstruction over Practically any Replication-Insertion Channel","year":2021,"downloads":9}