5 papers
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…
On optimal distinguishers for Planted Clique
Ansh Nagda, Prasad Raghavendra
In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a di…
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra +2
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to…
Robust recovery for stochastic block models, simplified and generalized
Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
We study the problem of : efficiently recovering communities in sparse stochastic block models in the presence of adversarial corruptions. In th…
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…