In classical statistical physics, a phase transition is understood by studying the geometry (the zero-set) of an associated polynomial (the partition function). In this thesis, we will show that one can exploit this notion of phase transitions algorithmically, and conversely exploit the analysis of algorithms to understand phase transitions.

As applications, we give efficient deterministic approximation algorithms (FPTAS) for counting $q$-colorings, and for computing the partition function of the Ising model.

Spin systems originated in statistical physics as tools for modeling phase transitions in magnets. However, they have since been used to model complex systems arising in several other fields of study (e.g., in Bayesian inference and in the theory of social networks), so that various computational problems associated with them have received much attention in the literature. A lot of progress in the study of these problems has relied upon ideas from statistical physics; one example of this interplay has been the discovery of tight connections between the computational complexity of these problems and the phenomenon of phase transitions that many spin systems exhibit. Conversely, algorithmic ideas have also helped in the study of the phase transition phenomenon.

This thesis presents two lines of work that fit into this theme. The first considers the approximation of the partition function, a pivotal quantity associated with spin systems. Here, we obtain—in various settings—deterministic polynomial time algorithms for approximating the partition function in the so called uniqueness regime, and thus strengthen the algorithmic side of the tight correspondence between phase transitions and the computational complexity of the partition function.

The second line of work is concerned with the complexity of exact computation of various natural mean observables of spin systems, e.g., the magnetization in the Ising model. We relate these questions to the location of the complex zeros of the partition function, which have been studied in statistical physics because of their connections to the existence of phase transitions, and have been the subject of various celebrated results (such as the Lee–Yang theorem and the Heilmann–Lieb theorem). By proving a novel extension of the Lee–Yang theorem, we show that the magnetization of the ferromagnetic Ising model is indeed as hard to compute as the partition function (i.e., #P–hard). We also obtain similar results for the monomer–dimer model.

Reaction networks are a powerful tool for modeling the behavior of a wide variety of real-world systems, including population dynamics and chemical processes, as well as algorithms for sampling combinatorial objects. While many such systems have well-understood equilibrium states, the long-standing conjecture that these states will always be achieved remains open. This thesis presents the class of simplicial reaction networks, which includes a wide variety of natural combinatorial examples of use in theoretical computer science. It shows how simplicial structures can be used to understand and control the equilibrium behavior of the network as a whole, and discusses related progress towards the Global Attractor Conjecture. Finally, this thesis presents additional work exploring combinatorial approaches to the Inverse Eigenvalue Problem on graphs, including the randomized Zero Forcing algorithm and a lower bound for the Minimum Rank problem.

Stochastic Local Search and the Lovasz Local Lemma

by

Fotios Iliopoulos

Doctor of Philosophy in Computer Science

University of California, Berkeley

Professor Alistair Sinclair, Chair

This thesis studies randomized local search algorithms for finding solutions of constraint satisfaction problems inspired by and extending the Lovasz Local Lemma (LLL).

The LLL is a powerful probabilistic tool for establishing the existence of objects satisfying certain properties (constraints). As a probability statement it asserts that, given a family of “bad” events, if each bad event is individually not very likely and independent of all but a small number of other bad events, then the probability of avoiding all bad events is strictly positive. In a celebrated breakthrough, Moser and Tardos made the LLL constructive for any product probability measure over explicitly presented variables. Specifically, they proved that whenever the LLL condition holds, their Resample algorithm, which repeatedly selects any occurring bad event and resamples all its variables according to the measure, quickly converges to an object with desired properties.

In this dissertation we present a framework that extends the work of Moser and Tardos and can be used to analyze arbitrary, possibly complex, focused local search algorithms, i.e., search algorithms whose process for addressing violated constraints, while local, is more sophisticated than obliviously resampling their variables independently of the current configuration. We give several applications of this framework, notably a new vertex coloring algorithm for graphs with sparse vertex neighborhoods that uses a number of colors that matches the algorithmic barrier for random graphs, and polynomial time algorithms for the celebrated (non-constructive) results of Kahn for the Goldberg-Seymour and List-Edge-Coloring Conjectures.

Finally, we introduce a generalization of Kolmogorov’s notion of commutative algorithms, cast as matrix commutativity, and show that their output distribution approximates the so-called “LLL-distribution”, i.e., the distribution obtained by conditioning on avoiding all bad events. This fact allows us to consider questions such as the number of possible distinct final states and the probability that certain portions of the state space are visited by a local search algorithm, extending existing results for the Moser-Tardos algorithm to commutative algorithms.

The random-cluster model has been widely studied as a unifying framework for spin systems, random graphs and electrical networks. The random-cluster model on a graph~$G=(V,E)$ with parameters $p\in(0,1)$ and $q>0$ assigns to each subgraph $(V,A \subseteq E)$ a probability proportional to $p^{|A|}(1-p)^{|E|-|A|} q^{c(A)}$, where $c(A)$ is the number of connected components in~$(V,A)$. When $q=1$ this model corresponds to the standard \textit{bond percolation model}. For integer $q \ge 2$ the random-cluster model is closely related to the classical ferromagnetic \textit{$q$-state Ising/Potts model}. When $q\rightarrow 0$, the set of weak limits that arise contains the uniform measures over the spanning trees, spanning forests and connected subgraphs of $G$.

In this thesis we investigate the dynamics of the random-cluster model. While dynamics for the Ising/Potts model have been widely studied, random-cluster dynamics have so far largely resisted analysis. We focus on two canonical cases: the case when $G$ is the complete graph on $n$ vertices, known as the \textit{mean-field model}, and the case when $G$ is the infinite 2-dimensional lattice graph $Z^2$. Mean-field models have historically proven to be a useful starting point in understanding dynamics on more general graphs. In statistical mechanics, however, probabilistic models are most frequently studied in the setting of infinite lattice graphs; understanding random-cluster dynamics in $Z^2$ is thus of foremost importance.

In the first part of this thesis we establish the mixing time of Chayes-Machta dynamics in the the mean-field case. For $q \in (1,2]$ we prove that the mixing time is $\Theta(\log n)$ for all $p \neq p_c(q)$, where $p = p_c(q)$ is the critical value corresponding to the emergence of a ``giant'' component. For $q > 2$, we identify a critical window $(p_s,p_S)$ of the parameter $p$ around $p_c(q)$ in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is $\Theta(\log n)$ when $p \not\in [p_s,p_S]$ and $\exp(\Omega(\sqrt{n}))$ when $p \in (p_s,p_S)$. We also show that the mixing time is $\Theta(n^{1/3})$ for $p=p_s$ and $\Theta(\log n)$ for $p=p_S$. In addition, we prove that the Glauber dynamics undergoes a similar exponential slowdown in $(p_s,p_S)$.

The second part of this thesis focuses on the analysis of the Glauber dynamics of the random-cluster model in the case where the underlying graph is an $n \times n$ box in the Cartesian lattice~$Z^2$. Our main result is a tight $\Theta(n^2\log n)$ bound for the mixing time at all values of the model parameter~$p$ except the critical point $p=p_c(q)$, and for all values of~$q\ge 1$.

We study fundamental problems for static and mobile networks.

First, we consider the random geometric graph model, which is a well-known model for static

wireless networks. In this model,

n nodes are distributed independently and uniformly at random

in the d-dimensional torus of volume n and edges are added between

pairs of nodes whose Euclidean distance is at most some parameter r. We consider the case where r is a sufficiently large constant

so that a so-called giant component (a connected component with \Theta(n) nodes) exists with high probability.

In this setting, we show that the graph distance between every pair of

nodes whose Euclidean distance is sufficiently large is only a constant factor larger than their Euclidean distance.

This result gives, as a corollary, that the diameter of the giant component is \Theta(n^{1/d}/r).

Then, we apply this result to analyze the performance of a broadcast algorithm known as the push algorithm.

In this algorithm, at each discrete time step, each informed node chooses

a neighbor independently and uniformly at random and informs it. We show that the push algorithm informs all nodes of the giant component

of a random geometric graph within a number of steps that is only a constant factor larger then the diameter of the giant component.

In the second part of the thesis, we consider a model of mobile graphs that we call mobile geometric graphs, and which is an extension of

the random geometric graph model to the setting where nodes are not static but are moving in space in continuous time.

In this model, we start with a random geometric graph and let the nodes move as independent Brownian motions.

Then, at any given time, there exists an edge between every pair of nodes whose Euclidean distance at that time

is at most r. This model has been recently used as a model for mobile wireless networks.

We study four fundamental problems in this model: detection (the time until a target point---fixed or moving---is

within distance r of some node of the graph); coverage (the time until all points inside

a finite box are detected by the graph);

percolation (the time until a given node belongs to the giant component of the graph) and

broadcast (the time until all nodes of the graph receive a piece of information that was initially known by a single node).

We obtain precise asymptotics for these quantities by combining ideas from stochastic geometry,

coupling and multi-scale analysis.

Finally, in the last part of the thesis, we revisit the push algorithm described above and study its performance in general regular graphs.

Our goal is to understand the relation between the performance of the push algorithm and the vertex expansion of the graph.

We prove an upper bound for the runtime of this algorithm that depends on the vertex expansion of the graph and is tight up to polylogarithmic factors.

Then, we show that there exists a substantial difference between the impact of vertex expansion and edge expansion on the performance of the push algorithm.

In particular, we prove the existence of regular graphs (which are also vertex transitive) that have constant vertex expansion and for which the runtime of

the push algorithm is a factor of \Omega(log n) slower than on any regular graph with constant edge expansion.