Sarah Cannon, UC Berkeley. “Markov Chains, Programmable Matter, and Emergent Behavior”

Position:  NSF Postdoctoral Research Fellow

Current Institution:  University of California, Berkeley

Abstract:  Markov Chains, Programmable Matter, and Emergent Behavior

How can collections of simple computational elements accomplish complicated system-level goals? This question motivates the study of programmable matter swarm robotics and even biological systems such as ant colonies. In simplified settings, we’ve shown that simple collections of abstract particles executing our local stochastic algorithms can accomplish remarkable global objectives, including the fundamental behaviors of compression separation and alignment. In several of our algorithms, changing just a single parameter results in a different, but equally desirable, emergent global behavior. Because our distributed algorithms come from Markov chains, we can use tools and insights from Markov chain analysis to predict and rigorously explain their behavior.

Sarah Cannon is an National Science Foundation (NSF) Mathematical Sciences Postdoctoral Research Fellow at the University of California, Berkeley. She recently completed a PhD in algorithms, combinatorics, and optimization at Georgia Tech, where she was an NSF Graduate Research Fellow and a Clare Boothe Luce Outstanding Graduate Fellow. She received a Simons Award for Graduate Students in Theoretical Computer Science. Previously, she received a master’s degree in mathematics and the foundations of computer science from the University of Oxford in 2013 and a bachelor’s degree in mathematics from Tufts University in 2012.