Title: Fixed-Magnetization Spin Models and Their Application to Programmable Matter

Date: Tuesday, June 10, 2025
Time: 10:00am-11:30am (Eastern Time)
Location (in-person): Klaus 2100
Location (virtual): https://gatech.zoom.us/j/92872403045

Shunhao Oh
PhD Student in Computer Science (Theory)
School of Computer Science
Georgia Institute of Technology

Committee:
Dr. Dana Randall (Advisor) - School of Computer Science, Georgia Institute of Technology
Dr. Will Perkins - School of Computer Science, Georgia Institute of Technology
Dr. Zongchen Chen - School of Computer Science, Georgia Institute of Technology
Dr. Daniel I. Goldman - School of Physics, Georgia Institute of Technology
Dr. Andrea W. Richa - School of Computing and Augmented Intelligence, Arizona State University

Abstract:
Nature provides many examples where large swarms of organisms organize and exhibit large-scale collective behaviors. Birds in a flock seem to make local adjustments to synchronize the direction of motion of the collective; some species of ants spontaneously form bridges or rafts by clinging onto their neighbors in bodies of water, despite its perils. Are these complex behaviors evidence of complex reasoning and coordination? Or can they be explained as emergent behaviors arising from far simpler, localized interactions, by agents acting independently, without a leader to direct them or any awareness of the collective?

This thesis focuses on questions at the interface between many domains of science and technology; how much might emergence play a role in collective coordination, and how can we design systems that coordinate using these insights? Our work strongly relates to swarm robotics, the study of how to design groups of robots that can operate without external infrastructure or centralized control. Desirable properties of such models of distributed computation include agents having very limited computational capabilities and only local interactions.

We study self-organization in the context of self-organizing particle system on a lattice, where each site of an underlying lattice can hold at most one particle. These particles are anonymous but may switch between states, and can move stochastically between adjacent lattice nodes---these movements and state changes are then analyzed as a Markov chain. There are multiple examples of prior work implementing various collective behaviors under such assumptions, like compression and aggregation, where particles collect closely together, or separation, where particles group with their own kind. This thesis generalizes some of these existing results, while developing new applications like alignment, where individuals are upon a common orientation, sorting, a generalization of separation where particles organize themselves spatially in various configurations, and foraging, where particles collectively respond to the presence or absence of environental stimuli.

To formally analyze these models and give rigorous mathematical explanations of their outcomes, we make the connection from these programmable matter systems to spin models from physics. We apply existing techniques from statistical physics used to study such spin models, while at the same time developing extensions of these tools to better suit our line of work. Fixed-magnetization spin models refer to spin models where a hard constraint is imposed on the quantities of each type of spin. These models are notoriously difficult to analyze compared to their traditional variable-magnetization counterparts, as existing statistical physics tools are often ill-equipped to deal with fixed-magnetization settings. Consequently, we make significant advances in the application of these tools for fixed-magnetization variants of commonly-studied spin models like the Ising, Potts and Blume-Capel models.