5 citations · 12 across the 22 of their papers we have counts for
7 papers · 1 filter
Pseudo-deterministic Streaming
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty +1
A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Clas…
Lifting Sum-of-Squares Lower Bounds: Degree- to Degree-
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
The degree- Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, S…
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;…
High-Dimensional Expanders from Expanders
Siqi Liu, Sidhanth Mohanty, Elizabeth Yang
We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to…
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…
-Ramanujan Graphs
Sidhanth Mohanty, Ryan O'Donnell
Let be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If is a finite graph covered by , it is said to be -Ramanujan i…