1 citations · 1 across the 8 of their papers we have counts for
4 papers · 1 filter
Circuit complexity lower bounds for quantum spin glasses
Omar Al-Ghattas, David Gamarnik
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum -spin glasses, ra…
The stochastic block model has the overlap graph property for modularity
Shankar Bhamidi, David Gamarnik, Remco van der Hofstad +4
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to…
Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data
Youssef Chaabouni, David Gamarnik
We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of low…
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach
We study the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs . Recently, Chatterjee and…