Hardness conjecture from zeros of the complex-valued Ising partition function
Hardness conjecture from zeros of the complex-valued Ising partition function
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Andreas Galanis, Leslie Ann Goldberg and Andrés Herrera-Poyatos, “The complexity of approximating the complex-valued Ising model on bounded degree graphs”, arXiv:2105.00287 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.