@ARTICLE{ref:CDRV22,
  author =	 {Mahdi Cheraghchi and Joseph Downs and Jo\~{a}o Ribeiro
                  and Alexandra Veliche},
  title =	 {Mean-Based Trace Reconstruction over Oblivious Synchronization Channels},
  year =	 2022,
  journal={IEEE Transactions on Information Theory}, 
  url_Paper =	 {https://arxiv.org/abs/2102.09490},
  url_Link = {https://ieeexplore.ieee.org/document/9743284},
  doi = {10.1109/TIT.2022.3157383},
  abstract =	 {Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors.
It is known that $\exp(\Theta(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.
We introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits.
This general class captures all previously considered synchronization channels.
We show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\exp(O(n^{1/3}))$ traces suffice for this task.}
}

{"_id":"cF3seZScKR8pSjp38","bibbaseid":"cheraghchi-downs-ribeiro-veliche-meanbasedtracereconstructionoveroblivioussynchronizationchannels-2022","author_short":["Cheraghchi, M.","Downs, J.","Ribeiro, J.","Veliche, A."],"bibdata":{"bibtype":"article","type":"article","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 Oblivious Synchronization Channels","year":"2022","journal":"IEEE Transactions on Information Theory","url_paper":"https://arxiv.org/abs/2102.09490","url_link":"https://ieeexplore.ieee.org/document/9743284","doi":"10.1109/TIT.2022.3157383","abstract":"Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors. It is known that $\\exp(Θ(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. We introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits. This general class captures all previously considered synchronization channels. We show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\\exp(O(n^{1/3}))$ traces suffice for this task.","bibtex":"@ARTICLE{ref:CDRV22,\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 Oblivious Synchronization Channels},\n year =\t 2022,\n journal={IEEE Transactions on Information Theory}, \n url_Paper =\t {https://arxiv.org/abs/2102.09490},\n url_Link = {https://ieeexplore.ieee.org/document/9743284},\n doi = {10.1109/TIT.2022.3157383},\n abstract =\t {Mean-based reconstruction is a fundamental, natural approach to worst-case trace reconstruction over channels with synchronization errors.\nIt is known that $\\exp(\\Theta(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.\nIn 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.\nWe introduce oblivious synchronization channels, which map each input bit to an arbitrarily distributed sequence of replications and insertions of random bits.\nThis general class captures all previously considered synchronization channels.\nWe show that for any oblivious synchronization channel whose output length follows a sub-exponential distribution either mean-based trace reconstruction is impossible or $\\exp(O(n^{1/3}))$ traces suffice for this task.}\n}\n\n","author_short":["Cheraghchi, M.","Downs, J.","Ribeiro, J.","Veliche, A."],"key":"ref:CDRV22","id":"ref:CDRV22","bibbaseid":"cheraghchi-downs-ribeiro-veliche-meanbasedtracereconstructionoveroblivioussynchronizationchannels-2022","role":"author","urls":{" paper":"https://arxiv.org/abs/2102.09490"," link":"https://ieeexplore.ieee.org/document/9743284"},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["mean","based","trace","reconstruction","over","oblivious","synchronization","channels","cheraghchi","downs","ribeiro","veliche"],"title":"Mean-Based Trace Reconstruction over Oblivious Synchronization Channels","year":2022,"downloads":12}