Approximate Trace Reconstruction and Related Results

Abstract

Trace reconstruction is the problem of estimating an unknown string of bits \(x \in \{0,1\}^n\) from noisy copies generated by independently deleting each bit of \(x\) with some known constant probability \(q\). The classic question is how many copies must be observed to reconstruct \(x\) with high probability. The current sample complexity upper bound for trace reconstruction is \( \exp(O(n^{1/3})) \) and the lower bound is \(\Omega(n^{\frac{3}{2}}/\log(n)^{16})\), signifying a wide information-theoretical gap. This thesis focuses mainly on the sample complexity of two variants of trace reconstruction. In approximate trace reconstruction, instead of reconstructing \(x\) exactly, the goal is for fixed \(\epsilon > 0\), to reconstruct a \(1-\epsilon\) fraction of \(x\) with high probability. Formally, we explore algorithms \(A\) that take as input \(T\) observed samples \(X_1,...,X_T\) and output a prediction \(A(X_1,...,X_T) = x_{\mathrm{pred}}\) such that \(P\Big(d(x_{\mathrm{pred}},x) \le \epsilon n \Big) \ge 1-\delta\), where d is a distance metric. This work first puts the approximate trace reconstruction problem in the context of the current worst-case reconstruction algorithms. Then, we focus on approximate reconstruction of a specific subsets of strings, namely strings with long runs of consecutive 1s or 0s and strings with high density regions of bits. We present polynomial time algorithms for approximate reconstruction for each of these different regimes. We also provide constructions to prove a lower bound on the number of traces necessary for \(o(1)\) approximate trace reconstruction. The second variant we consider is the exact reconstruction setting, in a case where the deletions are not independent, and specifically when the deletions of bits \(2k\) and \(2k+1\) are not independent. In this setting, we show that \(\exp(O(n^{1/3}\log(n)))\) traces are sufficient for exact trace reconstruction, and these results extend to the setting where non-overlapping sets of a constant number of bits are deleted non-independently.