3 papers
cs.DS2026
Quasipolynomial Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
We show that trace reconstruction on n-bit strings is possible using a quasipolynomial number of traces, for any retention probability p that is at least inverse polylogarithmic in…
cs.DS2025
New Bounds for Circular Trace Reconstruction
Arnav Burudgunte, Paul Valiant, Hongao Wang
The ''trace reconstruction'' problem asks, given an unknown binary string and a channel that repeatedly returns ''traces'' of with each bit randomly deleted with some proba…
cs.LG2025
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
Maryam Aliakbarpour, Arnav Burudgunte, Clément Cannone +1
We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios…