Andrea Montanari

activity

20152026

most citedExtremal Cuts of Sparse Random Graphs

108 citations · 112 across the 8 of their papers we have counts for

collaborators

Showing math.PRShow all

2 papers · 1 filter

math.PR2024★ 1 cited

Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time?

Andrea Montanari, Kangjie Zhou

Given $d$ -dimensional standard Gaussian vectors $x_{1}, \dots, x_{n}$ , we consider the set of all empirical distributions of its $m$ -dimensional projections, f…

math.PR2015★ 108 cited

Extremal Cuts of Sparse Random Graphs

Amir Dembo, Andrea Montanari, Subhabrata Sen

For Erdős-Rényi random graphs with average degree $γ$ , and uniformly random $γ$ -regular graph on $n$ vertices, we prove that with high probability the size of both the Max-Cut and…