Showing 2024Show all
3 papers · 1 filter
cs.IT2024
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…
cs.DS2024
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…
cs.LG2024
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…