Substring Density Estimation from Traces

Kayvon Mazooji, Ilan Shomorony

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that exp(Õ(n1/5)) traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map"that indicates the locations of each length-k substring throughout s. We show that ?-2 • poly(n) traces suffice to recover the density map with error at most ?. As a result, when restricted to a set of source strings whose minimum "density map distance"is at least 1/poly(n), the trace reconstruction problem can be solved with polynomially many traces.

Original languageEnglish (US)
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages803-808
Number of pages6
ISBN (Electronic)9781665475549
DOIs
StatePublished - 2023
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China
Duration: Jun 25 2023Jun 30 2023

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2023-June
ISSN (Print)2157-8095

Conference

Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period6/25/236/30/23

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Substring Density Estimation from Traces'. Together they form a unique fingerprint.

Cite this