Abstract: Spin systems (also known as Markov random fields) originated in statistical physics as tools for modeling phase transitions in magnets. However, they have since been used to model complex systems arising in several other fields of study (e.g., in the study of social networks and in machine learning), so that various computational problems associated with them have received much...