Georgia Institute of Technology College of Sciences

Programmable matter explores how collections of computationally limited agents acting locally and asynchronously can achieve some useful coordinated behavior.  We take a stochastic approach using techniques from randomized algorithms and statistical physics to develop distributed algorithms for emergent collective behaviors that give guarantees and are robust to failures.  By analyzing the Gibbs distribution of various fixed-magnetization models from equilibrium statistical mechanics, we show that particles moving stochastically according to local affinities can solve various useful collective tasks. Finally, we will briefly introduce new tools that may prove fruitful in nonequilibrium settings as well.

Work of Levin and Przytycki shows that if two non-special rational
functions f and g of degree $> 1 $over $\mathbb{C}$ share the same set of
preperiodic points, there are $m$, $n$, and $r$ such that $f^m g^n = f^r$.
In other words, $f$ and $g$ nearly commute.  One might ask if there are
other sorts of relations non-special rational functions $f$ and $g$ over $\mathbb{C}$
might satisfy when they do not share the same set of preperiodic
points.  We will present a recent proof of Beaumont that shows that
they may not, that if f and g do not share the same set of preperiodic
points, then they generate a free semi-group under composition.  The
proof builds on work of Bell, Huang, Peng, and the speaker, and uses a
ping-pong lemma similar to the one used by Tits in his proof of the
Tits alternative for finitely generated linear groups.

We consider the strong parity edge coloring problem, which aims to color the edges of a graph G so that in each open walk on G, some color appears an odd number of times.  We show that this problem is equivalent to the problem of embedding a graph in a vector space over F2 so that the number of difference vectors attained at the edges is minimized. Using this equivalence, we achieve the following:

1. We characterize graphs on n vertices that can be embedded with ceil(log_2 n) difference vectors, answering a question of Bunde, Milans, West, and Wu.

2. We show that the number of colors needed for a strong parity edge coloring of K_{s,t} is given by the Hopf-Stiefel function, confirming a conjecture of Bunde, Milans, West, and Wu.

3. We find an asymptotically optimal embedding for the power of a path.

This talk is based on joint work with Sergey Norin and Doug West.

Dehn surgery is a fundamental construction in topology where one removes a neighborhood of a knot from the three-sphere and reglues to obtain a new three-manifold. The Cosmetic Surgery Conjecture predicts two different surgeries on the same non-trivial knot always gives different three-manifolds. We discuss how gauge theory, in particular, the Chern-Simons functional, can help approach this problem. This technique allows us to solve the conjecture in essentially all but one case. This is joint work with Ali Daemi and Mike Miller Eismeier.