DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.30

New Bounds for Circular Trace Reconstruction

Authors: Arnav Burudgunte, Paul Valiant, and Hongao Wang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The "trace reconstruction" problem asks, given an unknown binary string x and a channel that repeatedly returns "traces" of x with each bit randomly deleted with some probability p, how many traces are needed to recover x? There is an exponential gap between the best known upper and lower bounds for this problem. Many variants of the model have been introduced in hopes of motivating or revealing new approaches to narrow this gap. We study the variant of circular trace reconstruction introduced by Narayanan and Ren (ITCS 2021), in which traces undergo a random cyclic shift in addition to random deletions. We show an improved lower bound of Ω̃(n⁵) for circular trace reconstruction. This contrasts with the (previously) best known lower bounds of Ω̃(n³) in the circular case and Ω̃(n^{3/2}) in the linear case. Our bound shows the indistinguishability of traces from two sparse strings x,y that each have a constant number of nonzeros. Can this technique be extended significantly? How hard is it to reconstruct a sparse string x under a cyclic deletion channel? We resolve these questions by showing, using Fourier techniques, that Õ(n⁶) traces suffice for reconstructing any constant-sparse string in a circular deletion channel, in contrast to the best known upper bound of exp(Õ(n^{1/3})) for general strings in the circular deletion channel. This shows that new algorithms or new lower bounds must focus on non-constant-sparse strings.

Cite as

Arnav Burudgunte, Paul Valiant, and Hongao Wang. New Bounds for Circular Trace Reconstruction. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{burudgunte_et_al:LIPIcs.ITCS.2026.30,
  author =	{Burudgunte, Arnav and Valiant, Paul and Wang, Hongao},
  title =	{{New Bounds for Circular Trace Reconstruction}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.30},
  URN =		{urn:nbn:de:0030-drops-253176},
  doi =		{10.4230/LIPIcs.ITCS.2026.30},
  annote =	{Keywords: Trace reconstruction, algorithmic statistics, Fourier analysis}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.98

Optimal Sub-Gaussian Mean Estimation in Very High Dimensions

Authors: Jasper C.H. Lee and Paul Valiant

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We address the problem of mean estimation in very high dimensions, in the high probability regime parameterized by failure probability δ. For a distribution with covariance Σ, let its "effective dimension" be d_eff = {Tr(Σ)}/{λ_{max}(Σ)}. For the regime where d_eff = ω(log^2 (1/δ)), we show the first algorithm whose sample complexity is optimal to within 1+o(1) factor. The algorithm has a surprisingly simple structure: 1) re-center the samples using a known sub-Gaussian estimator, 2) carefully choose an easy-to-compute positive integer t and then remove the t samples farthest from the origin and 3) return the sample mean of the remaining samples. The core of the analysis relies on a novel vector Bernstein-type tail bound, showing that under general conditions, the sample mean of a bounded high-dimensional distribution is highly concentrated around a spherical shell.

Cite as

Jasper C.H. Lee and Paul Valiant. Optimal Sub-Gaussian Mean Estimation in Very High Dimensions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 98:1-98:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ITCS.2022.98,
  author =	{Lee, Jasper C.H. and Valiant, Paul},
  title =	{{Optimal Sub-Gaussian Mean Estimation in Very High Dimensions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{98:1--98:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.98},
  URN =		{urn:nbn:de:0030-drops-156942},
  doi =		{10.4230/LIPIcs.ITCS.2022.98},
  annote =	{Keywords: High-dimensional mean estimation}
}

Search Results

Documents authored by Valiant, Paul

New Bounds for Circular Trace Reconstruction

Abstract

Cite as

Optimal Sub-Gaussian Mean Estimation in Very High Dimensions

Abstract

Cite as

Thanks for your feedback!

Could not send message