Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.
Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 3verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
Upper bounds on ultrametric OGPs at levels 1 and 2 for symmetric binary perceptrons are approximately 1.6578 and 1.6219, closely matching the 3rd and 4th lifting-level parametric RDT estimates, supporting conjectures that the algorithmic threshold equals the infinite-level limits of both frameworks.
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.
citing papers explorer
-
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.
-
Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection
Upper bounds on ultrametric OGPs at levels 1 and 2 for symmetric binary perceptrons are approximately 1.6578 and 1.6219, closely matching the 3rd and 4th lifting-level parametric RDT estimates, supporting conjectures that the algorithmic threshold equals the infinite-level limits of both frameworks.
-
Lower bound on the mixing time of $p$-spin glasses
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.