ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let d≥4d\geq 4, let λc(d)\lambda_c(d) denote the critical fugacity for the hardcore model on the dd-regular tree, and let λ\lambda satisfy λc(d)<λ\lambda_c(d)<\lambda. 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 NP=RP\mathrm{NP}=\mathrm{RP}, there does not exist a fully polynomial approximation scheme for the partition function of the hardcore model with fugacity λ\lambda on graphs of maximum degree at most dd.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.