7 papers
Circuit complexity lower bounds for quantum spin glasses
Omar Al-Ghattas, David Gamarnik
The paper proves that preparing near‑optimal low‑energy states of random quantum p‑spin glass Hamiltonians requires circuits of at least logarithmic depth, showing that shallow qua…
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 a…
Spin Glass Transitions Obstruct Decoded Quantum Interferometry
Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu
Quantum algorithms are believed to offer advantages in solving certain hard discrete optimization problems, yet identifying when such advantages persist in explicit distributions o…
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse…