
The degree splitting problem requires coloring the edges of a graph red or
blue such that each node has almost the same number of edges in each color, up
to a small additive discrepancy. The directed variant of the problem requires
orienting the edges such that each node has almost the same number of incoming
and outgoing edges, again up to a small additive discrepancy.
We present deterministic distributed algorithms for both variants, which
improve on their counterparts presented by Ghaffari and Su [SODA'17]: our
algorithms are significantly simpler and faster, and have a much smaller
discrepancy. This also leads to a faster and simpler deterministic algorithm
for $(2+o(1))\Delta$edgecoloring, improving on that of Ghaffari and Su.

A number of recent papers  e.g. Brandt et al. (STOC 2016), Chang et al.
(FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang &
Pettie (FOCS 2017)  have advanced our understanding of one of the most
fundamental questions in theory of distributed computing: what are the possible
time complexity classes of LCL problems in the LOCAL model? In essence, we have
a graph problem $\Pi$ in which a solution can be verified by checking all
radius$O(1)$ neighbourhoods, and the question is what is the smallest $T$ such
that a solution can be computed so that each node chooses its own output based
on its radius$T$ neighbourhood. Here $T$ is the distributed time complexity of
$\Pi$.
The time complexity classes for deterministic algorithms in boundeddegree
graphs that are known to exist by prior work are $\Theta(1)$, $\Theta(\log^*
n)$, $\Theta(\log n)$, $\Theta(n^{1/k})$, and $\Theta(n)$. It is also known
that there are two gaps: one between $\omega(1)$ and $o(\log \log^* n)$, and
another between $\omega(\log^* n)$ and $o(\log n)$. It has been conjectured
that many more gaps exist, and that the overall time hierarchy is relatively
simple  indeed, this is known to be the case in restricted graph families
such as cycles and grids.
We show that the picture is much more diverse than previously expected. We
present a general technique for engineering LCL problems with numerous
different deterministic time complexities, including $\Theta(\log^{\alpha}n)$
for any $\alpha\ge1$, $2^{\Theta(\log^{\alpha}n)}$ for any $\alpha\le 1$, and
$\Theta(n^{\alpha})$ for any $\alpha <1/2$ in the high end of the complexity
spectrum, and $\Theta(\log^{\alpha}\log^* n)$ for any $\alpha\ge 1$,
$\smash{2^{\Theta(\log^{\alpha}\log^* n)}}$ for any $\alpha\le 1$, and
$\Theta((\log^* n)^{\alpha})$ for any $\alpha \le 1$ in the low end; here
$\alpha$ is a positive rational number.

In this work we study the cost of local and global proofs on distributed
verification. In this setting the nodes of a distributed system are provided
with a nondeterministic proof for the correctness of the state of the system,
and the nodes need to verify this proof by looking at only their local
neighborhood in the system.
Previous works have studied the model where each node is given its own,
possibly unique, part of the proof as input. The cost of a proof is the maximum
size of an individual label. We compare this model to a model where each node
has access to the same global proof, and the cost is the size of this global
proof.
It is easy to see that a global proof can always include all of the local
proofs, and every local proof can be a copy of the global proof. We show that
there exists properties that exhibit these relative proof sizes, and also
properties that are somewhere in between. In addition, we introduce a new lower
bound technique and use it to prove a tight lower bound on the complexity of
reversing distributed decision and establish a link between communication
complexity and distributed proof complexity.

Distributed proofs are mechanisms enabling the nodes of a network to
collectivity and efficiently check the correctness of Boolean predicates on the
structure of the network, or on datastructures distributed over the nodes
(e.g., spanning trees or routing tables). We consider mechanisms consisting of
two components: a \emph{prover} assigning a \emph{certificate} to each node,
and a distributed algorithm called \emph{verifier} that is in charge of
verifying the distributed proof formed by the collection of all certificates.
In this paper, we show that many network predicates have distributed proofs
offering a high level of redundancy, explicitly or implicitly. We use this
remarkable property of distributed proofs for establishing perfect tradeoffs
between the \emph{size of the certificate} stored at every node, and the
\emph{number of rounds} of the verification protocol. If we allow every node to
communicate to distance at most $t$, one might expect that the certificate
sizes can be reduced by a multiplicative factor of at least~$t$. In trees,
cycles and grids, we show that such tradeoffs can be established for \emph{all}
network predicates, i.e., it is always possible to linearly decrease the
certificate size. In arbitrary graphs, we show that any part of the
certificates common to all nodes can be evenly redistributed among these nodes,
achieving even a better tradeoff: this common part of the certificate can be
reduced by the size of a smallest ball of radius $t$ in the network.
In addition to these general results, we establish several upper and lower
bounds on the certificate sizes used for distributed proofs for spanning trees,
minimumweight spanning trees, diameter, additive and multiplicative spanners,
and more, improving and generalizing previous results from the literature.

We present a randomized distributed algorithm that computes a
$\Delta$coloring in any noncomplete graph with maximum degree $\Delta \geq 4$
in $O(\log \Delta) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized
algorithm that computes a $\Delta$coloring in $O((\log \log n)^2)$ rounds when
$\Delta \in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log
\Delta)$round algorithm of Panconesi and Srinivasan~[STOC'1993], which has
remained the state of the art for the past 25 years. Moreover, the latter
algorithm gets (exponentially) closer to an $\Omega(\log\log n)$ round lower
bound of Brandt et al.~[STOC'16].

LCLs or locally checkable labelling problems (e.g. maximal independent set,
maximal matching, and vertex colouring) in the LOCAL model of computation are
very wellunderstood in cycles (toroidal 1dimensional grids): every problem
has a complexity of $O(1)$, $\Theta(\log^* n)$, or $\Theta(n)$, and the design
of optimal algorithms can be fully automated.
This work develops the complexity theory of LCL problems for toroidal
2dimensional grids. The complexity classes are the same as in the
1dimensional case: $O(1)$, $\Theta(\log^* n)$, and $\Theta(n)$. However, given
an LCL problem it is undecidable whether its complexity is $\Theta(\log^* n)$
or $\Theta(n)$ in 2dimensional grids.
Nevertheless, if we correctly guess that the complexity of a problem is
$\Theta(\log^* n)$, we can completely automate the design of optimal
algorithms. For any problem we can find an algorithm that is of a normal form
$A' \circ S_k$, where $A'$ is a finite function, $S_k$ is an algorithm for
finding a maximal independent set in $k$th power of the grid, and $k$ is a
constant.
Finally, partially with the help of automated design tools, we classify the
complexity of several concrete LCL problems related to colourings and
orientations.

We extend the notion of distributed decision in the framework of distributed
network computing, inspired by recent results on socalled distributed graph
automata. We show that, by using distributed decision mechanisms based on the
interaction between a prover and a disprover, the size of the certificates
distributed to the nodes for certifying a given network property can be
drastically reduced. For instance, we prove that minimum spanning tree can be
certified with $O(\log n)$bit certificates in $n$node graphs, with just one
interaction between the prover and the disprover, while it is known that
certifying MST requires $\Omega(\log^2 n)$bit certificates if only the prover
can act. The improvement can even be exponential for some simple graph
properties. For instance, it is known that certifying the existence of a
nontrivial automorphism requires $\Omega(n^2)$ bits if only the prover can act.
We show that there is a protocol with two interactions between the prover and
the disprover enabling to certify nontrivial automorphism with $O(\log n)$bit
certificates. These results are achieved by defining and analysing a local
hierarchy of decision which generalizes the classical notions of
prooflabelling schemes and locally checkable proofs.

This work bridges the gap between distributed and centralised models of
computing in the context of sublineartime graph algorithms. A priori, typical
centralised models of computing (e.g., parallel decision trees or centralised
local algorithms) seem to be much more powerful than distributed
messagepassing algorithms: centralised algorithms can directly probe any part
of the input, while in distributed algorithms nodes can only communicate with
their immediate neighbours. We show that for a large class of graph problems,
this extra freedom does not help centralised algorithms at all: for example,
efficient stateless deterministic centralised local algorithms can be simulated
with efficient distributed messagepassing algorithms. In particular, this
enables us to transfer existing lower bound results from distributed algorithms
to centralised local algorithms.

We show that any randomised Monte Carlo distributed algorithm for the
Lov\'asz local lemma requires $\Omega(\log \log n)$ communication rounds,
assuming that it finds a correct assignment with high probability. Our result
holds even in the special case of $d = O(1)$, where $d$ is the maximum degree
of the dependency graph. By prior work, there are distributed algorithms for
the Lov\'asz local lemma with a running time of $O(\log n)$ rounds in
boundeddegree graphs, and the best lower bound before our work was
$\Omega(\log^* n)$ rounds [Chung et al. 2014].

The role of unique node identifiers in network computing is well understood
as far as symmetry breaking is concerned. However, the unique identifiers also
leak information about the computing environment  in particular, they provide
some nodes with information related to the size of the network. It was recently
proved that in the context of local decision, there are some decision problems
such that (1) they cannot be solved without unique identifiers, and (2) unique
node identifiers leak a sufficient amount of information such that the problem
becomes solvable (PODC 2013).
In this work we give study what is the minimal amount of information that we
need to leak from the environment to the nodes in order to solve local decision
problems. Our key results are related to scalar oracles $f$ that, for any given
$n$, provide a multiset $f(n)$ of $n$ labels; then the adversary assigns the
labels to the $n$ nodes in the network. This is a direct generalisation of the
usual assumption of unique node identifiers. We give a complete
characterisation of the weakest oracle that leaks at least as much information
as the unique identifiers.
Our main result is the following dichotomy: we classify scalar oracles as
large and small, depending on their asymptotic behaviour, and show that (1) any
large oracle is at least as powerful as the unique identifiers in the context
of local decision problems, while (2) for any small oracle there are local
decision problems that still benefit from unique identifiers.

This work studies distributed algorithms for locally optimal loadbalancing:
We are given a graph of maximum degree $\Delta$, and each node has up to $L$
units of load. The task is to distribute the load more evenly so that the loads
of adjacent nodes differ by at most $1$.
If the graph is a path ($\Delta = 2$), it is easy to solve the fractional
version of the problem in $O(L)$ communication rounds, independently of the
number of nodes. We show that this is tight, and we show that it is possible to
solve also the discrete version of the problem in $O(L)$ rounds in paths.
For the general case ($\Delta > 2$), we show that fractional load balancing
can be solved in $\operatorname{poly}(L,\Delta)$ rounds and discrete load
balancing in $f(L,\Delta)$ rounds for some function $f$, independently of the
number of nodes.

We study the problem of finding large cuts in $d$regular trianglefree
graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a
cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of
edges. We give a simpler algorithm that does much better: it finds a cut of
expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in
any $d$regular trianglefree graph there exists a cut of at least this size.
Our algorithm can be interpreted as a very efficient randomised distributed
algorithm: each node needs to produce only one random bit, and the algorithm
runs in one synchronous communication round. This work is also a case study of
applying computational techniques in the design of distributed algorithms: our
algorithm was designed by a computer program that searched for optimal
algorithms for small values of $d$.

By prior work, there is a distributed algorithm that finds a maximal
fractional matching (maximal edge packing) in $O(\Delta)$ rounds, where
$\Delta$ is the maximum degree of the graph. We show that this is optimal:
there is no distributed algorithm that finds a maximal fractional matching in
$o(\Delta)$ rounds.
Our work gives the first linearin$\Delta$ lower bound for a natural graph
problem in the standard model of distributed computingprior lower bounds for
a wide range of graph problems have been at best logarithmic in $\Delta$.

In the study of deterministic distributed algorithms it is commonly assumed
that each node has a unique $O(\log n)$bit identifier. We prove that for a
general class of graph problems, local algorithms (constanttime distributed
algorithms) do not need such identifiers: a port numbering and orientation is
sufficient.
Our result holds for socalled simple POcheckable graph optimisation
problems; this includes many classical packing and covering problems such as
vertex covers, edge covers, matchings, independent sets, dominating sets, and
edge dominating sets. We focus on the case of boundeddegree graphs and show
that if a local algorithm finds a constantfactor approximation of a simple
POcheckable graph problem with the help of unique identifiers, then the same
approximation ratio can be achieved on anonymous networks.
As a corollary of our result and by prior work, we derive a tight lower bound
on the local approximability of the minimum edge dominating set problem.
Our main technical tool is an algebraic construction of homogeneously ordered
graphs: We say that a graph is $(\alpha,r)$homogeneous if its nodes are
linearly ordered so that an $\alpha$ fraction of nodes have pairwise isomorphic
radius$r$ neighbourhoods. We show that there exists a finite
$(\alpha,r)$homogeneous $2k$regular graph of girth at least $g$ for any
$\alpha < 1$ and any $r$, $k$, and $g$.

We study distributed algorithms that find a maximal matching in an anonymous,
edgecoloured graph. If the edges are properly coloured with $k$ colours, there
is a trivial greedy algorithm that finds a maximal matching in $k1$
synchronous communication rounds. The present work shows that the greedy
algorithm is optimal in the general case: any algorithm that finds a maximal
matching in anonymous, $k$edgecoloured graphs requires $k1$ rounds.
If we focus on graphs of maximum degree $\Delta$, it is known that a maximal
matching can be found in $O(\Delta + \log^* k)$ rounds, and prior work implies
a lower bound of $\Omega(\polylog(\Delta) + \log^* k)$ rounds. Our work closes
the gap between upper and lower bounds: the complexity is $\Theta(\Delta +
\log^* k)$ rounds. To our knowledge, this is the first linearin$\Delta$ lower
bound for the distributed complexity of a classical graph problem.