3 Search Results for "Spang, Bruce"

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 Õ(n⁶) traces suffice for reconstructing any constant-sparse string in a circular deletion channel, in contrast to the best known upper bound of exp(Õ(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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.3
Near-Optimal Trace Reconstruction for Mildly Separated Strings

Authors: Anders Aamand, Allen Liu, and Shyam Narayanan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In the trace reconstruction problem our goal is to learn an unknown string x ∈ {0,1}ⁿ given independent traces of x. A trace is obtained by independently deleting each bit of x with some probability δ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability δ is constant. The best known upper bound and lower bounds are respectively exp(Õ(n^{1/5})) [Zachary Chase, 2021a] and ̃ Ω(n^{3/2}) [Zachary Chase, 2021b]. Our main result is that if the string x is mildly separated, meaning that the number of zeros between any two ones in x is at least polylog n, and if δ is a sufficiently small constant, then the trace reconstruction problem can be solved with O(n log n) traces and in polynomial time.
Cite as

Anders Aamand, Allen Liu, and Shyam Narayanan. Near-Optimal Trace Reconstruction for Mildly Separated Strings. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.ICALP.2025.3,
  author =	{Aamand, Anders and Liu, Allen and Narayanan, Shyam},
  title =	{{Near-Optimal Trace Reconstruction for Mildly Separated Strings}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.3},
  URN =		{urn:nbn:de:0030-drops-233801},
  doi =		{10.4230/LIPIcs.ICALP.2025.3},
  annote =	{Keywords: Trace Reconstruction, deletion channel, sample complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.46
Unconstraining Graph-Constrained Group Testing

Authors: Bruce Spang and Mary Wootters

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graph-constrained group testing. Graph-constrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology. The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graph-constrained group testing is near-optimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs. Finally, we provide empirical results which suggest that our connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.
Cite as

Bruce Spang and Mary Wootters. Unconstraining Graph-Constrained Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{spang_et_al:LIPIcs.APPROX-RANDOM.2019.46,
  author =	{Spang, Bruce and Wootters, Mary},
  title =	{{Unconstraining Graph-Constrained Group Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.46},
  URN =		{urn:nbn:de:0030-drops-112615},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.46},
  annote =	{Keywords: Group testing, network tomography, random graphs}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2019

  • Refine by Author
  • 1 Aamand, Anders
  • 1 Burudgunte, Arnav
  • 1 Liu, Allen
  • 1 Narayanan, Shyam
  • 1 Spang, Bruce
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic inference problems
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Fourier analysis
  • 1 Group testing
  • 1 Trace Reconstruction
  • 1 Trace reconstruction
  • 1 algorithmic statistics
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact