5 citations · 12 across the 22 of their papers we have counts for
11 papers · 1 filter
Sparsifying Cayley Graphs on Every Group
Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty +2
A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a cut (or spectral) sparsifier which prese…
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…
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the de…
On statistical inference when fixed points of belief propagation are unstable
Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfa…
List Decodable Mean Estimation in Nearly Linear Time
Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau
Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a h…
Local Statistics, Semidefinite Programming, and Community Detection
Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertic…
Explicit near-Ramanujan graphs of every degree
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
For every constant and , we give a deterministic -time algorithm that outputs a -regular graph on vertices that is -near-Ramanujan;…
The SDP value for random two-eigenvalue CSPs
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, ``two-eigenvalue 2CSPs''. We show…
Algorithms for Noisy Broadcast under Erasures
Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty
The noisy broadcast model was first studied in [Gallager, TranInf'88] where an -character input is distributed among processors, so that each processor receives one input bi…
On Sketching the to norms
Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff
We initiate the study of data dimensionality reduction, or sketching, for the norms. Given an matrix , the norm, denoted $\|A\|_{q \to p} = \sup_{…