Fine-Grained Complexity Across the Computational Phase Transition
cs.CC, cs.DS, math.PR
Submitted: 2026-11-02
Updated: 2026-11-02
Terminology
Sources
- Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
- On the self-intersection time of non-backtracking random walks
- Rapid Mixing on Random Regular Graphs beyond Uniqueness
- Rapid Mixing at the Uniqueness Threshold
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains
- Rapid mixing of Glauber dynamics via spectral independence for all degrees
- Improved Mixing of Critical Hardcore Model
- Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
- Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
- On expectations and variances in the hard-core model on bounded degree graphs
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
- Critical window for approximate counting in dense Ising models
- Quantitative Small Subgraph Conditioning
- Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
- FPTAS for #BIS with Degree Bounds on One Side
- Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
- The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
- Distribution of the magnetization of the critical Ising model on sparse random graphs
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?