Given a large graph G and k agents on this graph, we consider the Voronoi tessellation induced by the graph distance. Each agent gets control of the portion of the graph that is closer to itself than to any other agent. We study the limit law of the vector Vor: = (V1/n, V2/n, …, Vk/n), whose i'th coordinate records the fraction of vertices of G controlled by the i'th agent, as n tends to infinity. We show that if G is a uniform random tree, and the agents are placed uniformly at random, the limit law of Vor is uniform on the (k – 1)-dimensional simplex. In particular, when k = 2, the two agents each get a uniform random fraction of the territory. In fact, we prove the result directly on the Brownian continuum random tree (CRT), and we also prove the same result for a “higher genus” analogue of the CRT that we call the continuum random unicellular map, indexed by a genus parameter g ≥ 0. As a key step of independent interest, we study the case when G is a random planar embedded graph with a finite number of faces. The main idea of the proof is to show that Vor has the same distribution as another partition of mass Int: = (I1/n, I2/n, …, Ik/n) where Ij is the contour length separating the i-th agent from the next one in clockwise order around the graph.

For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.

In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in ϕ nO(logn) steps where ϕ is an upper bound on the random edge weight density. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.

The rotor walk on a graph is a deterministic analogue of random walk. Each vertex is equipped with a rotor, which routes the walker to the neighboring vertices in a fixed cyclic order on successive visits. We consider rotor walk on an infinite rooted tree, restarted from the root after each escape to infinity. We prove that the limiting proportion of escapes to infinity equals the escape probability for random walk, provided only finitely many rotors send the walker initially toward the root. For independently and identically distributed random initial rotor directions on a regular tree, the limiting proportion of escapes is either zero or the random walk escape probability, and undergoes a discontinuous phase transition between the two as the distribution is varied. In the critical case there are no escapes, but the walker's maximum distance from the root grows doubly exponentially with the number of visits to the root. We also prove that there exist trees of bounded degree for which the proportion of escapes eventually exceeds the escape probability by arbitrarily large $o(1)$ functions. No larger discrepancy is possible, while for regular trees, the discrepancy is at most logarithmic.

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability which permits routing, both for the hypercube and for the d-dimensional mesh. We use tools from percolation theory to show that in the d-dimensional mesh, once a giant component appears --- efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location then that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph Gn,p.