
Computational phase transitions in sparse planted problems?
In recent times the cavity method, a statistical physicsinspired heuris...
read it

Highgirth nearRamanujan graphs with lossy vertex expansion
Kahale proved that linear sized sets in dregular Ramanujan graphs have ...
read it

List Decodable Mean Estimation in Nearly Linear Time
Learning from data in the presence of outliers is a fundamental problem ...
read it

Pseudodeterministic Streaming
A pseudodeterministic algorithm is a (randomized) algorithm which, when...
read it

Local Statistics, Semidefinite Programming, and Community Detection
We propose a new hierarchy of semidefinite programming relaxations for i...
read it

Lifting SumofSquares Lower Bounds: Degree2 to Degree4
The degree4 SumofSquares (SoS) SDP relaxation is a powerful algorithm...
read it

Explicit nearRamanujan graphs of every degree
For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)time...
read it

HighDimensional Expanders from Expanders
We present an elementary way to transform an expander graph into a simpl...
read it

The SDP value for random twoeigenvalue CSPs
We precisely determine the SDP value (equivalently, quantum value) of la...
read it

XRamanujan Graphs
Let X be an infinite graph of bounded degree; e.g., the Cayley graph of ...
read it

Algorithms for Noisy Broadcast under Erasures
The noisy broadcast model was first studied in [Gallager, TranInf'88] wh...
read it

On Sketching the q to p norms
We initiate the study of data dimensionality reduction, or sketching, fo...
read it
Sidhanth Mohanty
is this you? claim profile