
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.

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].

The present paper studies local distributed graph problems in highly dynamic
networks. We define a (in our view) natural generalization of static graph
problems to the dynamic graph setting. For some parameter $T>0$, the set of
admissible outputs of nodes in a $T$dynamic solution for a given graph problem
at some time $t$ is defined by the dynamic graph topology in the time interval
$[tT,t]$. The guarantees of a $T$dynamic solution become stronger the more
stable the graph remains during the interval $[tT,t]$ and they coincide with
the definition of the static graph problem if the graph is static throughout
the interval. We further present an abstract framework that allows to develop
distributed algorithms for a given dynamic graph problem. For some $T>0$, the
algorithms always output a valid $T$dynamic solution of the given graph
problem. Further, if a constant neighborhood around some part of the graph is
stable during an interval $[t_1,t_2]$, the algorithms compute a static solution
for this part of the graph throughout the interval $[t_1+T',t_2]$ for some
$T'>0$. Ideally $T$ and $T'$ are of the same asymptotic order as the time
complexity for solving the given graph problem in static networks.
We apply our generic framework to two classic distributed symmetry breaking
problems: the problem of computing a (degree+1)vertex coloring and the problem
of computing a maximal independent set (MIS) of the network graph. For both
problems, we obtain distributed algorithms that always output a valid $O(\log
n)$dynamic solution. Further, if some part of the graph and its
$O(1)$neighborhood remain stable for some interval $[t_1,t_2]$, for the given
part of the graph, the algorithms compute a valid static solution for the two
problems that remains stable throughout an interval $[t_1+O(\log n),t_2]$.

The algorithmic smallworld phenomenon, empirically established by Milgram's
letter forwarding experiments from the 60s, was theoretically explained by
Kleinberg in 2000. However, from today's perspective his model has several
severe shortcomings that limit the applicability to realworld networks. In
order to give a more convincing explanation of the algorithmic smallworld
phenomenon, we study decentralized greedy routing in a more flexible random
graph model (geometric inhomogeneous random graphs) which overcomes all
previous shortcomings. Apart from exhibiting good properties in theory, it has
also been extensively experimentally validated that this model reasonably
captures realworld networks.
In this model, the greedy routing protocol is purely distributed as each
vertex only needs to know information about its direct neighbors. We prove that
it succeeds with constant probability, and in case of success almost surely
finds an almost shortest path of length {\theta}(loglog n), where our bound is
tight including the leading constant. Moreover, we study natural local patching
methods which augment greedy routing by backtracking and which do not require
any global knowledge. We show that such methods can ensure success probability
1 in an asymptotically tight number of steps.
These results also address the question of Krioukov et al. whether there are
efficient local routing protocols for the internet graph. There were promising
experimental studies, but the question remained unsolved theoretically. Our
results give for the first time a rigorous and analytical affirmative answer.

This paper is centered on the complexity of graph problems in the
wellstudied LOCAL model of distributed computing, introduced by Linial [FOCS
'87]. It is widely known that for many of the classic distributed graph
problems (including maximal independent set (MIS) and $(\Delta+1)$vertex
coloring), the randomized complexity is at most polylogarithmic in the size $n$
of the network, while the best deterministic complexity is typically
$2^{O(\sqrt{\log n})}$. Understanding and narrowing down this exponential gap
is considered to be one of the central longstanding open questions in the area
of distributed graph algorithms. We investigate the problem by introducing a
complexitytheoretic framework that allows us to shed some light on the role of
randomness in the LOCAL model. We define the SLOCAL model as a sequential
version of the LOCAL model. Our framework allows us to prove completeness
results with respect to the class of problems which can be solved efficiently
in the SLOCAL model, implying that if any of the complete problems can be
solved deterministically in $\log^{O(1)} n$ rounds in the LOCAL model, we can
deterministically solve all efficient SLOCALproblems (including MIS and
$(\Delta+1)$coloring) in $\log^{O(1)} n$ rounds in the LOCAL model. We show
that a rather rudimentary looking graph coloring problem is complete in the
above sense: Color the nodes of a graph with colors red and blue such that each
node of sufficiently large polylogarithmic degree has at least one neighbor of
each color. The problem admits a trivial zeroround randomized solution. The
result can be viewed as showing that the only obstacle to getting efficient
determinstic algorithms in the LOCAL model is an efficient algorithm to
approximately round fractional values into integer values.

We show an $\Omega\big(\Delta^{\frac{1}{3}\frac{\eta}{3}}\big)$ lower bound
on the runtime of any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$graph coloring algorithm in a weak
variant of the \LOCAL\ model.
In particular, given a network graph \mbox{$G=(V,E)$}, in the weak \LOCAL\
model nodes communicate in synchronous rounds and they can use unbounded local
computation. We assume that the nodes have no identifiers, but that instead,
the computation starts with an initial valid vertex coloring. A node can
\textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its
neighbors and receives the \textbf{set of messages} sent to it by its
neighbors. That is, if two neighbors of a node $v\in V$ send the same message
to $v$, $v$ will receive this message only a single time; without any further
knowledge, $v$ cannot know whether a received message was sent by only one or
more than one neighbor.
Neighborhood graphs have been essential in the proof of lower bounds for
distributed coloring algorithms, e.g., \cite{linial92,Kuhn2006On}. Our proof
analyzes the recursive structure of the neighborhood graph of the respective
model to devise an $\Omega\big(\Delta^{\frac{1}{3}\frac{\eta}{3}}\big)$ lower
bound on the runtime for any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$graph coloring algorithm.
Furthermore, we hope that the proof technique improves the understanding of
neighborhood graphs in general and that it will help towards finding a lower
(runtime) bound for distributed graph coloring in the standard \LOCAL\ model.
Our proof technique works for oneround algorithms in the standard \LOCAL\
model and provides a simpler and more intuitive proof for an existing
$\Omega(\Delta^2)$ lower bound.

A bounded, Riemann integrable and measurable set $K\subset \mathbb{R}^d$,
which fulfills \[\sum\limits_{\gamma\in\Gamma}\mathbb{1}_K(x\gamma)=k\text{
almost everywhere, $x\in\mathbb{R}^d$}\] for a lattice
$\Gamma\subset\mathbb{R}^d$ is called $k$tiling. If $K\subset\mathbb{R}^d$ is
$k$tiling $L^2(K)$ will admit a Riesz basis of exponentials. We use this
result to construct generalized Riesz wavelet bases of $L^2(\mathbb{R}^2)$,
arising from the action of suitable subsets of the affine group. One example of
our construction is the first known shearlet Riesz basis.

In the classic gossipbased model of communication for disseminating
information in a network, in each time unit, every node $u$ is allowed to
contact a single random neighbor $v$. If $u$ knows the data (rumor) to be
disseminated, it disperses it to $v$ (known as PUSH) and if it does not, it
requests it from $v$ (known as PULL). While in the classic gossip model, each
node is only allowed to contact a single neighbor in each time unit, each node
can possibly be contacted by many neighboring nodes.
In the present paper, we consider a restricted model where at each node only
one incoming request can be served. As long as only a single piece of
information needs to be disseminated, this does not make a difference for push
requests. It however has a significant effect on pull requests. In the paper,
we therefore concentrate on this weaker pull version, which we call 'restricted
pull'.
We distinguish two versions of the restricted pull protocol depending on
whether the request to be served among a set of pull requests at a given node
is chosen adversarially or uniformly at random. As a first result, we prove an
exponential separation between the two variants. We show that there are
instances where if an adversary picks the request to be served, the restricted
pull protocol requires a polynomial number of rounds whereas if the winning
request is chosen uniformly at random, the restricted pull protocol only
requires a polylogarithmic number of rounds to inform the whole network.
Further, as the main technical contribution, we show that if the request to be
served is chosen randomly, the slowdown of using restricted pull versus using
the classic pull protocol can w.h.p. be upper bounded by $O(\Delta / \delta
\log n)$, where $\Delta$ and $\delta$ are the largest and smallest degree of
the network.