Towards Understanding the Complexity of the Ising Partition Function
summary
Study links Ising partition function (even-subgraph generating function) to topology and shows a concrete 4^g lower bound on the number of Pfaffian terms needed when restricted to orientation-derived matrices, using the Arf invariant formula and Fisher reductions; it identifies a parity matching problem that encodes embedded max-cut and resists algorithms faster than roughly 2^g because coefficient-extraction via isolation requires ~2^g interpolations; it also builds a construction representing any binary linear code’s weight enumerator as a four-dimensional determinant, which is provably intractable to compute in general.
AI-written summary · about