Mossel–Weitz–Wormald hardness conjecture for the hardcore model
Statement
Let , let denote the critical fugacity for the hardcore model on the -regular tree, and let satisfy . A fully polynomial approximation scheme (FPTAS) is an algorithm that approximates a partition function to arbitrary relative accuracy in time polynomial in the input size and the inverse accuracy.
Mossel–Weitz–Wormald conjecture. Unless , there does not exist a fully polynomial approximation scheme for the partition function of the hardcore model with fugacity on graphs of maximum degree at most .
The conjecture links the uniqueness threshold and computational hardness for approximate counting in the hardcore model. It was proposed in the context of exponential mixing-time lower bounds above the threshold; its resolution is not specified in the source.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.