research
∙
02/02/2023
Explicit two-sided unique-neighbor expanders
We study the problem of constructing explicit sparse imbalanced bipartit...
share
research
∙
10/01/2022
Local and global expansion in random geometric graphs
Consider a random geometric 2-dimensional simplicial complex X sampled a...
research
∙
07/22/2022
A simple and sharper proof of the hypergraph Moore bound
The hypergraph Moore bound is an elegant statement that characterizes th...
research
∙
11/22/2021
Testing thresholds for high-dimensional sparse random geometric graphs
In the random geometric graph model 𝖦𝖾𝗈_d(n,p), we identify each of our ...
research
∙
09/23/2021
Many nodal domains in random regular graphs
Let G be a random d-regular graph. We prove that for every constant α > ...
research
∙
06/24/2021
Certifying solution geometry in random CSPs: counts, clusters and balance
An active topic in the study of random constraint satisfaction problems ...
research
∙
01/26/2021
Computational phase transitions in sparse planted problems?
In recent times the cavity method, a statistical physics-inspired heuris...
research
∙
07/27/2020
High-girth near-Ramanujan graphs with lossy vertex expansion
Kahale proved that linear sized sets in d-regular Ramanujan graphs have ...
research
∙
05/20/2020
List Decodable Mean Estimation in Nearly Linear Time
Learning from data in the presence of outliers is a fundamental problem ...
research
∙
11/26/2019
Pseudo-deterministic Streaming
A pseudo-deterministic algorithm is a (randomized) algorithm which, when...
research
∙
11/05/2019
Local Statistics, Semidefinite Programming, and Community Detection
We propose a new hierarchy of semidefinite programming relaxations for i...
research
∙
11/04/2019
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
The degree-4 Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm...
research
∙
09/16/2019
Explicit near-Ramanujan graphs of every degree
For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)-time...
research
∙
07/24/2019
High-Dimensional Expanders from Expanders
We present an elementary way to transform an expander graph into a simpl...
research
∙
06/16/2019
The SDP value for random two-eigenvalue CSPs
We precisely determine the SDP value (equivalently, quantum value) of la...
research
∙
04/06/2019
X-Ramanujan Graphs
Let X be an infinite graph of bounded degree; e.g., the Cayley graph of ...
research
∙
08/02/2018
Algorithms for Noisy Broadcast under Erasures
The noisy broadcast model was first studied in [Gallager, TranInf'88] wh...
research
∙
06/17/2018