Approximate Trace Reconstruction via Median String (in Average-Case)

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Type: Preprint

Publication Date: 2021-01-01

Citations: 1

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

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Approximate Trace Reconstruction via Median String (In Average-Case).	2021	Diptarka Chakraborty Debarati Das Robert Krauthgamer
+	Approximate Trace Reconstruction	2020	Sami Davies Miklós Z. Rácz Cyrus Rashtchian Benjamin Schiffer
+	Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces	2021	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+	Approximate trace reconstruction of random strings from a constant number of traces	2021	Zachary Chase Yuval Peres
+	Approximate trace reconstruction of random strings from a constant number of traces	2021	Zachary Chase Yuval Peres
+	Approximate Trace Reconstruction: Algorithms	2021	Sami Davies Miklós Z. Rácz Benjamin Schiffer Cyrus Rashtchian
+ 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
+	Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem	2022	Ittai Rubinstein
+	Polynomial-time trace reconstruction in the smoothed complexity model	2020	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+ PDF Chat	Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice	2017	Yuval Peres Alex Zhai
+	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
+ PDF Chat	A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities	2024	Joey Rivkin Gregory Valiant Paul Valiant
+	Polynomial-time trace reconstruction in the low deletion rate regime	2020	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+	Substring Density Estimation from Traces	2022	Kayvon Mazooji Ilan Shomorony
+ PDF Chat	Subpolynomial trace reconstruction for random strings and arbitrary deletion probability	2020	Nina Holden Robin Pemantle Yuval Peres Alex Zhai
+	Optimal mean-based algorithms for trace reconstruction	2017	Anindya De Ryan O’Donnell Rocco A. Servedio
+ PDF Chat	Polynomial-time trace reconstruction in the smoothed complexity model	2021	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
+ PDF Chat	Polynomial-time trace reconstruction in the smoothed complexity model	2022	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha

Works That Cite This (1)

Action	Title	Year	Authors
+	Mean-Based Trace Reconstruction Over Oblivious Synchronization Channels	2022	Mahdi Cheraghchi Joseph Downs João Ribeiro Alexandra Veliche

Works Cited by This (15)

Action	Title	Year	Authors
+	Robust statistics on Riemannian manifolds via the geometric median	2008	P. Thomas Fletcher Suresh Venkatasubramanian Sarang Joshi
+	Geometric median in nearly linear time	2016	Michael B. Cohen Yin Tat Lee Gary L. Miller Jakub Pachocki Aaron Sidford
+ PDF Chat	Trace reconstruction with exp(O(n <sup>1/3</sup> )) samples	2017	Fëdor Nazarov Yuval Peres
+	Optimal mean-based algorithms for trace reconstruction	2017	Anindya De Ryan O’Donnell Rocco A. Servedio
+ PDF Chat	Assessing the best edit in perturbation-based iterative refinement algorithms to compute the median string	2019	Pedro Mirabal José Ignacio Abreu Salas Diego Seco
+ PDF Chat	Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice	2017	Yuval Peres Alex Zhai
+ PDF Chat	Beyond Trace Reconstruction: Population Recovery from the Deletion Channel	2019	Frank Ban Xi Chen Adam Freilich Rocco A. Servedio Sandip Sinha
+	Coded Trace Reconstruction	2020	Mahdi Cheraghchi Ryan Gabrys Olgica Milenković João Ribeiro
+	Lower bounds for trace reconstruction	2020	Nina Holden Russell Lyons
+	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance	2020	Elena Grigorescu Madhu Sudan Minshen Zhu