I will survey and try to explain the intuition behind several recent developments in the theory of distributed graph algorithms. I will focus on the LOCAL model, where the measure of interest is how far information has to be propagated in a communication network in order solve a given problem. The problems of interest will be locally checkable labelling problems (LCLs), a natural class of problems that allow distributed verification of proposed solutions.

I will discuss two recent papers in this field. First, we gave a lower bound showing that there exist LCL problems of ”intermediate” complexity, that is, complexity strictly between known complexity classes (Brandt et al., STOC 2016). The proof is by a new kind of simulation argument. Second, Chang et al. (FOCS 2016) showed that this lower bound implies an exponential separation between the randomized and deterministic LOCAL models. Chang et al. also show further connections between the randomized and deterministic models, and establish a useful speed-up simulation for the deterministic LOCAL model.