2024/12/01 by Joey Rivkin, Gregory Valiant, Rivkin, Joey +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2412.00674
openalex publication_date 2024/12/01 · openalex created_date 2024/12/05 · openalex updated_date 2026/07/28
We introduce the following natural generalization of trace reconstruction, parameterized by a deletion probability δ∈ (0,1) and length n: There is a length n string of probabilities, S=p1,…,pn, and each "trace" is obtained by 1) sampling a length n binary string whose ith coordinate is independently set to 1 with probability pi and 0 otherwise, and then 2) deleting each of the binary values independently with probability δ, and returning the corresponding binary string of length ≤ n. The goal is to recover an estimate of S from a set of independently drawn traces. In the case that all pi ∈ \0,1\ this is the standard trace reconstruction problem. We show two complementary results. First, for worst-case strings S and any deletion probability at least order 1/√(n), no algorithm can approximate S to constant ℓ_∞ distance or ℓ1 distance o(√ n) using fewer than 2Ω(√(n)) traces. Second -- as in the case for standard trace reconstruction -- reconstruction is easy for random S: for any sufficiently small constant deletion probability, and any ε>0, drawing each pi independently from the uniform distribution over [0,1], with high probability S can be recovered to ℓ1 error ε using poly(n,1/ε) traces and computation time. We show indistinguishability in our lower bound by regarding a complicated alternating sum (comparing two distributions) as the Fourier transformation of some function evaluated at ± π, and then showing that the Fourier transform decays rapidly away from zero by analyzing its moment generating function.