Computational transition at the uniqueness threshold

DOI10.1109/FOCS.2010.34MaRDI QIDQ6990319zbMATH OpenFDO

Authors Allan Sly

Publication date 29 April 2025

Full work available at URL https://doi.org/10.1109/FOCS.2010.34

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(28)

• A dichotomy for bounded degree graph homomorphisms with nonnegative weights
• Approximating queries on probabilistic graphs
• A spectral approach to approximately counting independent sets in dense bipartite graphs
• Glauber dynamics for the hard-core model on bounded-degree H-free graphs
• Hypergraph independence polynomials with a zero close to the origin
• Optimal mixing via tensorization for random independent sets on arbitrary trees
• Two-state spin systems with negative interactions
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Conjunctive queries on probabilistic graphs: the limits of approximability
• Two-state spin systems with negative interactions
• Influence maximization in Ising models
• On sampling from Ising models with spectral constraints
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Correlation decay and partition function zeros: algorithms and phase transitions
• Efficient quantum Gibbs samplers with Kubo-Martin-Schwinger detailed balance condition
• Inapproximability of counting hypergraph colourings
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Fast sampling via spectral independence beyond bounded-degree graphs
• Fast and perfect sampling of subgraphs and polymer systems
• Approximately counting independent sets of a given size in bounded-degree graphs
• A spectral independence view on hard spheres via block dynamics
• Pirogov-Sinai theory for the hard-core model beyond lattices
• Polynomial-time preparation of low-temperature Gibbs states for two-dimensional toric code
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Optimal mixing for randomly sampling edge colorings on trees down to the max degree
• Time lower bounds for the Metropolis process and simulated annealing
• Improved mixing of critical hardcore model
• Rapid mixing via coupling independence for spin systems with unbounded degree

This page was built for publication: Computational transition at the uniqueness threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6990319)