Title: Fixed-Magnetization Spin Models and Their Application to Programmable Matter
Date: Thursday, December 12, 2024
Time: 10:30am-12:00pm (Eastern Time)
Location (in-person): Klaus 2100
Location (virtual): https://gatech.zoom.us/j/98281241783?pwd=aafIkCljROmx2Od4Gk6eBxdowzpbB6.1
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:
Throughout nature we see examples where large swarms of small individual organisms organize and exhibit large scale collective behaviors. For example, birds in a flock seem to align with their nearest neighbors to produce global alignment for the collective, and ants spontaneously form bridges or rafts by clinging onto their neighbors in bodies of water, despite the perils. Are these complex, task-oriented behaviors evidence of complex reasoning and coordination? Or can they be explained as emergent behaviors arising from far simpler interactions, by agents acting locally and independently, without a leader to direct them or any awareness of the collective?
My research 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? We are specifically interested in models of distributed computation using agents with very limited computational capabilities that can nonetheless accomplish surprising collective tasks. The main assumptions are that our agents are anonymous (without identities), can only observe or interact with adjacent lattice nodes (or nodes within a constant distance), have at most constant memory, and do not have access to global information like the number of particles in the system.
We assume that we have a 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 a finite set of states, and can move stochastically between adjacent lattice nodes---these movements and state changes are then analyzed as a Markov chain. On such models, we study emergent behaviors like compression and aggregation, or the ability of a collective to collect closely together, separation, where different species interact but prefer their own kind, alignment, where individuals choose an orientation or color and want to agree locally, and hierarchical sorting, which we introduce to unify and generalize many of these previous models.
My dissertation will focus on developing and applying tools from statistical physics for studying the Markov chains representing such programmable matter systems. By making the connection to spin models from physics, we employ tools like Peierls arguments, cluster expansions for polymer models, and Pirogov-Sinai theory for our analysis. Fixed-magnetization spin models, as opposed to their variable-magnetization counterparts, are particularly applicable when it comes to understanding self-organizing particle systems, but are significantly more difficult to study, 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 studying fixed-magnetization variants of spin models, including the Ising, Potts and Blume-Capel models.