Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Ittai Rubinstein

Type: Preprint

Publication Date: 2022-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2207.11489

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces	2022	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+	Approximate Trace Reconstruction from a Single Trace	2022	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+	Approximate Trace Reconstruction via Median String (in Average-Case)	2021	Diptarka Chakraborty Debarati Das Robert Krauthgamer
+ PDF Chat	Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice	2017	Yuval Peres Alex Zhai
+	Average-case reconstruction for the deletion channel: subpolynomially many traces suffice	2017	Yuval Peres Alex Zhai
+	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability	2018	Nina Holden Robin Pemantle Yuval Peres
+	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability	2018	Nina Holden Robin Pemantle Yuval Peres Alex Zhai
+	Approximate Trace Reconstruction via Median String (In Average-Case).	2021	Diptarka Chakraborty Debarati Das Robert Krauthgamer
+	Coded trace reconstruction in a constant number of traces	2019	Joshua Brakensiek Ray Li Bruce Spang
+	Coded trace reconstruction in a constant number of traces	2019	Joshua Brakensiek Ray Li Bruce Spang
+	Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces	2021	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+	Lower bounds for trace reconstruction	2018	Nina Holden Russell Lyons
+	Efficient average-case population recovery in the presence of insertions and deletions	2019	Frank Ban Xi Chen Rocco A. Servedio Sandip Sinha
+	Efficient average-case population recovery in the presence of insertions and deletions	2019	Frank Ban Xi Chen Rocco A. Servedio Sandip Sinha
+	Average-case reconstruction for the deletion channel: subpolynomially many traces suffice	2017	Yuval Peres Alex Zhai
+	Lower bounds for trace reconstruction	2018	Nina Holden Russell Lyons
+	Optimal mean-based algorithms for trace reconstruction	2017	Anindya De Ryan O’Donnell Rocco A. Servedio
+	Lower bounds for trace reconstruction	2020	Nina Holden Russell Lyons
+	Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples	2016	Fëdor Nazarov Yuval Peres
+	Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples	2016	Fëdor Nazarov Yuval Peres

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors