Showing 2026Show all
2 papers · 1 filter
cs.LG2026
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman +1
We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured…
math.PR2026
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…