Buchumschlag

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Huang, Neng, Perkins, Will, Potechin, Aaron
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Probability Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Mysteries of MAX NAE-SAT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2020)

MAX BISECTION might be harder to approximate than MAX CUT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

A computational phase transition for learning-to-sample from Ising models
von: Risteski, Andrej, et al.
Veröffentlicht: (2026)

Fixed-magnetization Ising on random graphs up to reconstruction
von: Gheissari, Reza, et al.
Veröffentlicht: (2025)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
von: Kızıldağ, Eren C.
Veröffentlicht: (2023)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
von: Li, Tiange, et al.
Veröffentlicht: (2026)

The stochastic block model has the overlap graph property for modularity
von: Bhamidi, Shankar, et al.
Veröffentlicht: (2026)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Sharp Online Hardness for Large Balanced Independent Sets
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2025)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
von: Gamarnik, David, et al.
Veröffentlicht: (2026)

Detection of local geometry in random graphs: information-theoretic and computational limits
von: Bok, Jinho, et al.
Veröffentlicht: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

Inference of rankings planted in random tournaments
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Some easy optimization problems have the overlap-gap property
von: Li, Shuangping, et al.
Veröffentlicht: (2024)

Statistical inference of a ranked community in a directed graph
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Stable algorithms cannot reliably find isolated perceptron solutions
von: Gong, Shuyang, et al.
Veröffentlicht: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Sparsifying Suprema of Gaussian Processes
von: De, Anindya, et al.
Veröffentlicht: (2024)

Discrepancy Algorithms for the Binary Perceptron
von: Li, Shuangping, et al.
Veröffentlicht: (2024)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
von: Fu, Daniel, et al.
Veröffentlicht: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
von: R., Abhishek Hegade K., et al.
Veröffentlicht: (2025)

Parameter estimation for Gibbs distributions
von: Harris, David G., et al.
Veröffentlicht: (2020)

Testing Convex Truncation
von: De, Anindya, et al.
Veröffentlicht: (2023)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
von: Sohn, Youngtak, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Sampling Permutations with Cell Probes is Hard
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Hardness Results on Characteristics for Elastic-Degenerated Strings
von: Köppl, Dominik, et al.
Veröffentlicht: (2024)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Sumplete is Hard, Even with Two Different Numbers
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Hardness and Algorithmic Results for Roman \{3\}-Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)