Communication cost of consensus for nodes with limited memory.

Motivated by applications in wireless networks and the Internet of Things, we consider a model of n nodes trying to reach consensus with high probability on their majority bit. Each node i is assigned a bit at time 0 and is a finite automaton with m bits of memory (i.e., [Formula: see text] states) and a Poisson clock. When the clock of i rings, i can choose to communicate and is then matched to a uniformly chosen node j. The nodes j and i may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that, when [Formula: see text], consensus can be reached with linear communication cost, but this is impossible if [Formula: see text] A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.

Online learning with an almost perfect expert.

We study multiclass online learning, where a forecaster predicts a sequence of elements drawn from a finite set using the advice of n experts. Our main contributions are to analyze the scenario where the best expert makes a bounded number b of mistakes and to show that, in the low-error regime where [Formula: see text], the expected number of mistakes made by the optimal forecaster is at most [Formula: see text] We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.

Gravitational allocation on the sphere.

Given a collection L of n points on a sphere [Formula: see text] of surface area n, a fair allocation is a partition of the sphere into n parts each of area 1, and each is associated with a distinct point of L. We show that, if the n points are chosen uniformly at random and if the partition is defined by a certain "gravitational" potential, then the expected distance between a point on the sphere and the associated point of L is [Formula: see text] We use our result to define a matching between two collections of n independent and uniform points on the sphere and prove that the expected distance between a pair of matched points is [Formula: see text], which is optimal by a result of Ajtai, Komlós, and Tusnády.

Tractable near-optimal policies for crawling.

The problem of maintaining a local cache of n constantly changing pages arises in multiple mechanisms such as web crawlers and proxy servers. In these, the resources for polling pages for possible updates are typically limited. The goal is to devise a polling and fetching policy that maximizes the utility of served pages that are up to date. Cho and Garcia-Molina [(2003) ACM Trans Database Syst 28:390-426] formulated this as an optimization problem, which can be solved numerically for small values of n, but appears intractable in general. Here, we show that the optimal randomized policy can be found exactly in [Formula: see text] operations. Moreover, using the optimal probabilities to define in linear time a deterministic schedule yields a tractable policy that in experiments attains 99% of the optimum.

Rigorous location of phase transitions in hard optimization problems.

It is widely believed that for many optimization problems, no algorithm is substantially more efficient than exhaustive search. This means that finding optimal solutions for many practical problems is completely beyond any current or projected computational capacity. To understand the origin of this extreme 'hardness', computer scientists, mathematicians and physicists have been investigating for two decades a connection between computational complexity and phase transitions in random instances of constraint satisfaction problems. Here we present a mathematically rigorous method for locating such phase transitions. Our method works by analysing the distribution of distances between pairs of solutions as constraints are added. By identifying critical behaviour in the evolution of this distribution, we can pinpoint the threshold location for a number of problems, including the two most-studied ones: random k-SAT and random graph colouring. Our results prove that the heuristic predictions of statistical physics in this context are essentially correct. Moreover, we establish that random instances of constraint satisfaction problems have solutions well beyond the reach of any analysed algorithm.