Hardness conjecture from zeros of the complex-valued Ising partition function
Statement
Let be an integer with and let with . Let be a graph with maximum degree at most , and let denote its Ising partition function. The approximation problems and concern, respectively, approximating the norm and argument of this partition function. Hardness conjecture from zeros. If there is a graph with maximum degree at most such that
then the problems
are -hard. The surrounding discussion explains that a zero of the partition function can typically be used to implement the edge interaction , which yields hardness through the preceding lemma; the conjecture concerns the case where terminal-degree conditions are not established.
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.