The emergence of large-scale order from local interactions is a theme common to computing and living systems. The field of natural algorithms seeks to discover the fundamental principles that underlie this phenomenon in all its remarkable diversity. Can simple algorithmic rules explain how birds flock, how termites cooperate, how opinions polarize, how oscillators self-synchronize, how languages evolve through iterated learning, or how robustness emerges from adaptive systems? Beyond providing answers to these specific questions, the broader ambition of this project is to build bridges between the fields of algorithms and dynamical systems. Nearly all of the processes under consideration involve dynamic networks whose nodes represent autonomous agents interacting under time-varying topologies. It is often crucial to perform dimension reduction on such systems in a manner respectful of the dynamics. This task is approached through the lens of ?semantic renormalization,? a process that involves clustering dynamic graphs hierarchically. The theme of the project is highly multidisciplinary and forms the basis of graduate seminars and undergraduate projects with participation from computer science, mathematics, statistics, neuroscience, genomics, evolutionary biology, and mechanical engineering.
The project draws upon a wide range of techniques from areas as diverse as dynamical systems, machine learning, statistical mechanics, and network theory. It consists of four main parts: (a) ?iterated learning? features students who, acting as Bayesian agents, learn from teachers and then, in turn, become teachers themselves; (b) ?dynamic random walks? model random walks over graphs whose topology changes over time via a feedback loop; (c) ?opinion dynamics? investigates how autonomous agents can reach consensus through mutual, constrained interaction; (d) ?averaging systems? are coupled dynamical systems driven by convex combination updates over embedded dynamic networks.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
