6 papers
Average-Radius List-Decodability of Random Linear Codes
Venkatesan Guruswami, Shilun Li, Mihir Singhal
We prove that for every prime power and every , a random -linear code of rate is -average-radius list-decodable…
Nearly Time-Optimal Pure State Tomography with Pauli Measurements
Sabee Grewal, Meghal Gupta, William He +2
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given copies of…
The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions and over domains and , respectively. Their…
Tight bounds for stream decodable error-correcting codes
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message into a codeword. The receiver (Bob) decodes it corr…
Optimal quantile estimation: beyond the comparison model
Meghal Gupta, Mihir Singhal, Hongxun Wu
Estimating quantiles is one of the foundational problems of data sketching. Given elements from some universe of size arriving in a data stream, a qu…
Omnipredictors for Regression and the Approximate Rank of Convex Functions
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra +2
Consider the supervised learning setting where the goal is to learn to predict labels given points from a distribution. An \textit{omnipredictor} for a clas…