4 papers
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…
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…
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…
Sensor Placement for Learning in Flow Networks
Arnav Burudgunte, Arlei Silva
Large infrastructure networks (e.g. for transportation and power distribution) require constant monitoring for failures, congestion, and other adversarial events. However, assignin…