Extending extremal cut paper to max \(k\) xor, max \(q\)-cut, etc
(local algorithms are suboptimal on MAX \(k\) CUT, optimal value is related to parisi constant)
the actual original plots getting 0.7632 for SK
the parisi functional is convex so it has a unique minimum
alternate approach to calculating parisi formula at zero temp with dynamic programming, see
message passing algorithm to solve p spin glass hamiltonian (generalization of SK) – optimal without overlap gap
the parisi formula is differentiable, see
this intro is the most clear on explaining order parameters and replica symmetry breaking
the Sk model is full symmetry breaking, so the minimizing function has infinite number of ``jumps’’. Can prove it by always adding a jump near 1.
KSAT satisfying fraction relates to a spin glass problem too.
numerics for 2 XORSAT (SK) and 3 XORSAT (3-spin glass) using
properties of the parisi functional
the proof the parisi functional for mixed spin models
original parisi paper on approximating SK model, good visual of symmetry breaking
on phase transitions in xorsat
qaoa on mixed spin glass models…