Local interactions of uncoordinated individuals produce the collective behaviors of many biological systems, inspiring much of the current research in programmable matter. A striking example is the spontaneous assembly of fire ants into "bridges" comprising their own bodies to traverse obstacles and reach sources of food. Experiments and simulations suggest that, remarkably, these ants always form one bridge - instead of multiple, competing bridges - despite a lack of central coordination. We argue that the reliable formation of a single bridge does not require sophistication on behalf of the individuals by provably reproducing this behavior in a self-organizing particle system. We show that the formation of a single bridge by the particles is a statistical inevitability of their preferences to move in a particular direction, such as toward a food source, and their preference for more neighbors. Two parameters, η and β, reflect the strengths of these preferences and determine the Gibbs stationary measure of the corresponding particle system’s Markov chain dynamics. We show that a single bridge almost certainly forms when η and β are sufficiently large. Our proof introduces an auxiliary Markov chain, called an "occupancy chain," that captures only the significant, global changes to the system. Through the occupancy chain, we abstract away information about the motion of individual particles, but we gain a more direct means of analyzing their collective behavior. Such abstractions provide a promising new direction for understanding many other systems of programmable matter.

The foraging problem asks how a collective of particles with limited computational, communication and movement capabilities can autonomously compress around a food source and disperse when the food is depleted or shifted, which may occur at arbitrary times. We would like the particles to iteratively self-organize, using only local interactions, to correctly gather whenever a food particle remains in a position long enough and search if no food particle has existed recently. Unlike previous approaches, these search and gather phases should be self-induced so as to be indefinitely repeatable as the food evolves, with microscopic changes to the food triggering macroscopic, system-wide phase transitions. We present a stochastic foraging algorithm based on a phase change in the fixed magnetization Ising model from statistical physics: Our algorithm is the first to leverage self-induced phase changes as an algorithmic tool. A key component of our algorithm is a careful token passing mechanism ensuring a dispersion broadcast wave will always outpace a compression wave. We also present a highly structured alternative algorithm that gathers by incrementally building a spiral tightly wrapped around the food particle.

The field of randomized algorithms has benefitted greatly from insights from statistical physics. We give examples in two distinct settings. The first is in the context of Markov chain Monte Carlo algorithms, which have become ubiquitous across science and engineering as a means of exploring large configuration spaces. One of the most striking discoveries was the realization that many natural Markov chains undergo phase transitions, whereby they are efficient for some parameter settings and then suddenly become inefficient as a parameter of the system is slowly modified. The second is in the context of distributed algorithms for programmable matter. Self-organizing particle systems based on statistical models with phase changes have been used to achieve basic tasks involving coordination, movement, and conformation in a fully distributed, local setting. We briefly describe these two settings to demonstrate how computing and statistical physics together provide powerful insights that apply across multiple domains.

We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programmable matter. Such systems are composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational power. We consider heterogeneous particle systems of two different colors and prove that these systems can collectively separate into different color classes or integrate, indifferent to color. We accomplish both behaviors with the same fully distributed, local, stochastic algorithm. Achieving separation or integration depends only on a single global parameter determining whether particles prefer to be next to other particles of the same color or not; this parameter is meant to represent external, environmental influences on the particle system. The algorithm is a generalization of a previous distributed, stochastic algorithm for compression (PODC '16), which can be viewed as a special case of separation where all particles have the same color. It is significantly more challenging to prove that the desired behavior is achieved in the heterogeneous setting, however, even in the bichromatic case we focus on. This requires combining several new techniques, including the cluster expansion from statistical physics, a new variant of the bridging argument of Miracle, Pascoe and Randall (RANDOM '11), the high-temperature expansion of the Ising model, and careful probabilistic arguments.

The six-vertex model in statistical physics is a weighted generalization of the ice model on $\mathbb{Z}^2$ (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model depicts its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.

Many physical models undergo phase transitions as some parameter of the system is varied. This phenomenon has bearing on the convergence times for local Markov chains walking among the configurations of the physical system. One of the most basic examples of this phenomenon is the ferromagnetic Ising model on an n x n square lattice region Lambda with mixed boundary conditions. For this spin system, if we fix the spins on the top and bottom sides of the square to be + and the left and right sides to be -, a standard Peierls argument based on energy shows that below some critical temperature t_c, any local Markov chain M requires time exponential in n to mix. Spin glasses are magnetic alloys that generalize the Ising model by specifying the strength of nearest neighbor interactions on the lattice, including whether they are ferromagnetic or antiferromagnetic. Whenever a face of the lattice is bounded by an odd number of edges with ferromagnetic interactions, the face is considered frustrated because the local competing objectives cannot be simultaneously satisfied. We consider spin glasses with exactly four well-separated frustrated faces that are symmetric around the center of the lattice region under 90 degree rotations. We show that local Markov chains require exponential time for all spin glasses in this class. This class includes the ferromagnetic Ising model with mixed boundary conditions described above, where the frustrated faces are on the boundary. The standard Peierls argument breaks down when the frustrated faces are on the interior of Lambda and yields weaker results when they are on the boundary of Lambda but not near the corners. We show that there is a universal temperature T below which M will be slow for all spin glasses with four well-separated frustrated faces. Our argument shows that there is an exponentially small cut indicated by the free energy, carefully exploiting both entropy and energy to establish a small bottleneck in the state space to establish slow mixing.

We study rectangular dissections of an $n \times n$ lattice region into rectangles of area $n$, where $n=2^k$ for an even integer $k$. We show there is a natural edge-flipping Markov chain that connects the state space. A similar edge-flipping chain is known to connect the state space when restricted to dyadic tilings, where each rectangle is required to have the form $R = [s2^{u},(s+1)2^{u}]\times [t2^{v}, (t+1)2^{v}],$ where $s, t, u$, and $v$ are nonnegative integers. The mixing time of this Markov chain for general rectangular dissections remains open, while recent work by Cannon, Levin, and Stauffer [ Proceedings of APPROX/RANDOM 2017, pp. 34:1--34:21] gave a polynomial upper bound on the mixing time when restricting to dyadic tilings. We consider a weighted version of these Markov chains where, given a parameter $\lambda > 0,$ we would like to generate each rectangular dissection (or dyadic tiling) $\sigma$ with probability proportional to $\lambda^{|\sigma|},$ where $|\sigma|$ is the total edge length. We show there is a phase transition in the dyadic setting: when $\lambda < 1,$ the edge-flipping chain mixes in time $O(n^2)$, and when $\lambda > 1,$ the mixing time is $\exp(\Omega({n^2}))$. The behavior for general rectangular dissections is more subtle, and even establishing ergodicity of the chain requires a careful inductive argument. As in the dyadic case, we show that the edge-flipping Markov chain for rectangular dissections requires exponential time when $\lambda > 1$. Surprisingly, the chain also requires exponential time when $\lambda < 1$, which we show using a different argument. Simulations suggest that the chain converges quickly at the isolated point $\lambda =1$, but this case remains open.

Graded posets frequently arise throughout combinatorics, where it is natural to try to count the number of elements of a fixed rank. These counting problems are often #P-complete, so we consider approximation algorithms for counting and uniform sampling. We show that for certain classes of posets, biased Markov chains that walk along edges of their Hasse diagrams allow us to approximately generate samples with any fixed rank in expected polynomial time. Our arguments do not rely on the typical proofs of log-concavity, which are used to construct a stationary distribution with a specific mode in order to give a lower bound on the probability of outputting an element of the desired rank. Instead, we infer this directly from bounds on the mixing time of the chains through a method we call balanced bias. A noteworthy application of our method is sampling restricted classes of integer partitions of n. We give the first provably efficient Markov chain algorithm to uniformly sample integer partitions of n from general restricted classes. Several observations allow us to improve the efficiency of this chain to require O(n1/2 log(n)) space, and for unrestricted integer partitions, expected O(n9/4) time. Related applications include sampling permutations with a fixed number of inversions and lozenge tilings on the triangular lattice with a fixed average height.

Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large sets of configurations. The idea is to perform a random walk among the configurations so that even though only a very small part of the space is visited, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they change from being efficient to inefficient as some parameter of the system is modified, also revealing interesting properties of the underlying random structures. We will explore how phase transitions can provide valuable insights in three settings. First, they allow us to understand the limitations of certain classes of sampling algorithms, potentially leading to faster alternative approaches. Second, they reveal statistical properties of stationary distributions, giving insight into various interacting models. Example include colloids, or binary mixtures of molecules, segregation models, where individuals are more likely move when they are unhappy with their local demographics, and interacting particle systems from statistical physics. Last, they predict emergent phenomena that can be harnessed for the design of distributed algorithms for certain asynchronous models of programmable active matter. We will see how these three research threads are closely interrelated and inform one another. The talk will take a random walk through some of the results included in the references.

We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant-size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. The algorithm takes as input a bias parameter λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all λ > 5, there is a constant α > 1 such that at stationarity with all but exponentially small probability the particles are α-compressed, meaning the perimeter of the system configuration is at most α ⋅ pmin, where pmin is the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of λ in particular, for all 0 < λ < √2, there is a constant β < 1 such that at stationarity, with all but an exponentially small probability, the perimeter will be at least β ⋅ pmax, where pmax is the maximum possible perimeter.

Many statistical physics models are defined on an infinite lattice by taking appropriate limits of finite lattice regions, where a key consideration is how the boundaries are defined. For several models on planar lattices, such as 3-colorings and lozenge tilings, efficient sampling algorithms are known for regions with fixed boundary conditions, where the colors or tiles around the boundary are pre-specified [14], but much less is known about how to sample when these regions have free boundaries, where we want to include all configurations one could see within a finite window. We introduce a method using randomized extensions of a lattice region to relate sampling problems on regions with free boundaries to a constant number of sampling problems on larger regions with fixed boundaries. We demonstrate this principled approach to sample 3-colorings of regions of ℤ2 and lozenge tilings of regions of the triangular lattice, building on arguments for the fixed boundary cases due to Luby et al. [14]. Our approach also yields an efficient algorithm for sampling 3-colorings with free boundary conditions on regions with one reflex corner, the first such result for a nonconvex region. This approach can also be generalized to a broad class of mixed boundary conditions. Sampling for these families of regions is significant because it allows us to establish self-reducibility, giving the first algorithm to approximately count the total number of 3-colorings of rectangular lattice regions.

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a Schnyder wood that has proven powerful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a “triangle-reversing” chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that, when restricted to planar triangulations of maximum degree six, this Markov chain is rapidly mixing and we can approximately count 3-orientations. Next, we construct a triangulation with high degree on which this Markov chain mixes slowly. Finally, we consider an “edge-flipping” chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. We prove that this chain is always rapidly mixing.

We study rectangular dissections of an n × n lattice region into rectangles of area n, where n = 2k for an even integer k. We show that there is a natural edge-flipping Markov chain that connects the state space. A similar edge-flipping chain is also known to connect the state space when restricted to dyadic tilings, where each rectangle is required to have the form R = [s2u, (s + 1)2u] × [t2v, (t+1)2v], where s, t, u and v are nonnegative integers. The mixing time of these chains is open. We consider a weighted version of these Markov chains where, given a parameter λ > 0, we would like to generate each rectangular dissection (or dyadic tiling) σ with probability proportional to λ|σ|, where |σ| is the total edge length. We show there is a phase transition in the dyadic setting: when λ < 1, the edge-flipping chain mixes in time O(n2 log n), and when λ > 1, the mixing time is exp(Ω(n2)). Simulations suggest that the chain converges quickly when λ = 1, but this case remains open. The behavior for general rectangular dissections is more subtle, and even establishing ergodicity of the chain requires a careful inductive argument. As in the dyadic case, we show that the edge-flipping Markov chain for rectangular dissections requires exponential time when λ > 1. Surprisingly, the chain also requires exponential time when λ < 1, which we show using a different argument. Simulations suggest that the chain converges quickly at the isolated point λ = 1.

We show that for all sufficiently large $d$, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on ${\mathbb Z}^d$ admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in ${\mathbb Z}^d$, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex $v$ in the box, then the probability that $v$ gets color 0 is exponentially small in $d$. The proof proceeds through an analysis of a certain type of cutset separating $v$ from the boundary of the box and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on ${\mathbb Z}^d$. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus ${\mathbb Z}^d_n$. We show that there is a constant $\rho \approx 0.22$ such that for all even $n \geq 4$ and $d$ sufficiently large, if ${\mathcal M}$ is a Markov chain on the set of proper 3-colorings of ${\mathbb Z}^d_n$ that updates the color of at most $\rho n^d$ vertices at each step and whose stationary distribution is uniform, then the mixing time of ${\mathcal M}$ (the time taken for ${\mathcal M}$ to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in $n^{d-1}$.

The Schelling segregation model attempts to explain possible causes of racial segregation in cities. Schelling considered residents of two types, where everyone prefers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move, called the General Influence Model. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated (i.e., there will not be clustering) if the racial bias is sufficiently low. Next we show complementary results for two broad classes of influence functions: Increasing Bias Functions (IBF), where an individual's likelihood of moving increases each time someone of the same color leaves (this does not include Schelling's threshold models), and Threshold Bias Functions (TBF) with the threshold exceeding one half, reminiscent of the model Schelling originally proposed. For both classes (IBF and TBF), we show that when the bias is sufficiently high, the dynamics take exponential time to mix and we will have segregation and a large “ghetto” will form.

We study the mixing time of a Markov chain Mnn on permutations that performs nearest neighbor transpositions in the non-uniform setting, a problem arising in the context of self-organizing lists. We are given “positively biased” probabilities {pij ≥ 1/2} for all i < j and let pj,i = 1 − pj,i. In each step, the chain Mnn chooses two adjacent elements k, and ℓ and exchanges their positions with probability pℓ,k. Here we define two general classes and give the first proofs that the chain is rapidly mixing for both. In the first case we are given constants r1, … rn−1 with 1/2 ≤ ri ≤ 1 for all i and we set pi,j = ri for all i < j. In the second we are given a binary tree with n leaves labeled 1, … n and constants q1, … qn−1 associated with all of the internal vertices, and we let pi,j = qi⁁j for all i < j. Our bounds on the mixing time of Mnn rely on bijections between permutations, inversion tables and asymmetric simple exclusion processes (ASEPs) that allow us to express moves of the chain in the context of these other combinatorial families. We also demonstrate that the chain is not always rapidly mixing by constructing an example requiring exponential time to converge to equilibrium. This proof relies on a reduction to biased lattice paths in ℤ2.

No abstract available.

We consider the problem of approximately counting integral flows in a network. We show that there is a fully polynomial randomized approximation scheme (FPRAS) based on volume estimation if all capacities are sufficiently large, generalizing a result of Dyer, Kannan, and Mount [Random Structures Algorithms, 10 (1997), pp. 487–506]. We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums, and cell bounds may be arbitrary. We provide an FPRAS for this problem via a combination of dynamic programming and volume estimation. This generalizes an algorithm of Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291–310] for standard contingency tables, but the analysis here is considerably more intricate.

Monotonic surfaces spanning finite regions of ℤd arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. We explore how we can sample these surfaces when the distribution is biased to favor higher surfaces. We show that a natural local chain is rapidly mixing with any bias for regions in ℤ2, and for bias λ > d2 in ℤd, when d > 2. Moreover, our bounds on the mixing time are optimal on d-dimensional hyper-cubic regions. The proof uses a geometric distance function and introduces a variant of path coupling in order to handle distances that are exponentially large.

Adaptive power topology control (APTC) is a local algorithm for constructing a one-parameter family of θ-graphs, where each node increases power until it has a neighbor in every θ sector around it.We show it is possible to use such a local geometric θ-constraint to ensure full network connectivity, and consider tradeoffs between assumptions about the wireless footprint and constraints on the boundary nodes. In particular, we show that if the boundary nodes can communicate with neighboring boundary nodes and all interior nodes satisfy a θI π constraint, we can guarantee connectivity for any arbitrary wireless footprint. If we relax the boundary assumption and instead impose a θB < 3π/2 constraint on the boundary nodes, together with the θI < π constraint on interior nodes, we can guarantee full network connectivity using only a "weak-monotonicity" footprint assumption. The weak-monotonicity model, introduced herein, is much less restrictive than the disk model of coverage and captures aspects of the spatial correlations inherent in signal propagation and noise. We show that under the idealized disk model of coverage, APTC constructs graphs that are sparse. Finally, we show that if the wireless footprint has sufficiently small "eccentricity", then there is some θ for which greedy geometric routing always succeeds.

We consider the problem of approximately counting integral flows in a network. We show that there is an fpras based on volume estimation if all capacities are sufficiently large, generalising a result of Dyer, Kannan and Mount (1997). We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums and cell bounds may be arbitrary. We provide an fpras for this problem via a combination of dynamic programming and volume estimation. This generalises an algorithm of Cryan and Dyer (2002) for standard contingency tables, but the analysis here is considerably more intricate.

In this paper, we introduce the notion of a Markov chain and explore how it can be used to sample from a large set of configurations. Our primary focus is determining how quickly a Markov chain "mixes," or converges to its stationary distribution, as this is the key factor in the running time. We provide an overview of several techniques used to establish good bounds on the mixing time. The applications are mostly chosen from statistical physics, although the methods are much more general.

We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. In this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski rental-like problems.

Consider the following Markov chain, whose states are all domino tilings of a 2n× 2n chessboard: starting from some arbitrary tiling, pick a 2×2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes $90^{\rm o}$ in place. Repeat many times. This process is used in practice to generate a random tiling and is a widely used tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. This paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

Staircase walks are lattice paths from (0,0) to (2n,0) which take diagonal steps and which never fall below the x-axis. A path hitting the x-axis /spl kappa/ times is assigned a weight of /spl lambda//sup /spl kappa//, where /spl lambda/>0. A simple local Markov chain, which connects the state space and converges to the Gibbs measure (which normalizes these weights) is known to be rapidly mixing when /spl lambda/=1, and can easily be shown to be rapidly mixing when /spl lambda/1, known in the statistical physics community as adsorbing staircase walks. The main new ingredient is a decomposition technique which allows us to analyze the Markov chain in pieces, applying different arguments to analyze each piece.

This paper develops a new technique for bounding the mixing rate of a Markov chain by decomposing the state space into factors. The first application is an efficient Monte Carlo Markov chain algorithm for generating random three-colorings of 2-dimensional lattice regions. This provides a rigorous tool for studying some properties of the 3-state Potts model and the ice model from statistical mechanics. As a second application, we develop similar techniques to bound the mixing rate of a Metropolis sampling algorithm by a type of "temperature factorization". Both factorization theorems work by using known mixing properties of related Markov chains to establish the efficiency of a new sampling algorithm.

Consider the following Markov chain, whose states are all domino tilings of a 2n/spl times/2n chessboard: starting from some arbitrary tiling, pick a 2/spl times/2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling and is a key tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. The paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

We study the problem of counting the number of matchings of given cardinalitg in a d-dimensional rectangular lattice.This problem arises in several models in statistical phgsics, including monomer-dimer systems and cell-cluster theory.A classical algorithm due to Fisher, Kasteleyn and Temperley counts perfect matchings exactly in two dimensions, but is not applicable in higher dimensions and does not allow one to count matchings of arbitrary cardinality.In this paper, we present the first eficient approximation algorithms for counting matchings of arbitrary cardinality in (i) d-dimensional '>en"odic" lattices (i.e., with wrap-around edges) in any fixed dimension d; and (ii) two-dimensional lattices with "fixed boundary conditions" (i.e., no wrap-around edges).Our technique generalizes to approximately counting matchings in any bipartite graph that is the Cayley graph of some finite group.