Reproduce “Fine-Grained Complexity Across the Computational Phase Transition” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Zhe Ju, Jingcheng Liu, Yitong Yin

The authors analyze sampling independent sets in the hard-core model, where fugacity controls their weight. They show that above the tree-uniqueness threshold, Glauber mixing has exponential scale exp{Θ(nδ²/d)}, with matching bounds for fixed degree. At fixed degree, δ≈n⁻¹/³ gives exp{Θ(n¹/³/d)} mixing time up to polynomial factors. Their hardness implications apply only to specified distance schedules.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.