
Many ant species employ distributed population density estimation in
applications ranging from quorum sensing [Pra05], to task allocation [Gor99],
to appraisal of enemy colony strength [Ada90]. It has been shown that ants
estimate density by tracking encounter rates  the higher the population
density, the more often the ants bump into each other [Pra05,GPT93].
We study distributed density estimation from a theoretical perspective. We
prove that a group of anonymous agents randomly walking on a grid are able to
estimate their density within a small multiplicative error in few steps by
measuring their rates of encounter with other agents. Despite dependencies
inherent in the fact that nearby agents may collide repeatedly (and, worse,
cannot recognize when this happens), our bound nearly matches what would be
required to estimate density by independently sampling grid locations.
From a biological perspective, our work helps shed light on how ants and
other social insects can obtain relatively accurate density estimates via
encounter rates. From a technical perspective, our analysis provides new tools
for understanding complex dependencies in the collision probabilities of
multiple random walks. We bound the strength of these dependencies using
$local\ mixing\ properties$ of the underlying graph. Our results extend beyond
the grid to more general graphs and we discuss applications to size estimation
for social networks and density estimation for robot swarms.

We give a new randomized distributed algorithm for $(\Delta+1)$coloring in
the LOCAL model, running in $O(\sqrt{\log \Delta})+ 2^{O(\sqrt{\log \log n})}$
rounds in a graph of maximum degree~$\Delta$. This implies that the
$(\Delta+1)$coloring problem is easier than the maximal independent set
problem and the maximal matching problem, due to their lower bounds of $\Omega
\left( \min \left( \sqrt{\frac{\log n}{\log \log n}}, \frac{\log \Delta}{\log
\log \Delta} \right) \right)$ by Kuhn, Moscibroda, and Wattenhofer [PODC'04].
Our algorithm also extends to listcoloring where the palette of each node
contains $\Delta+1$ colors. We extend the set of distributed symmetrybreaking
techniques by performing a decomposition of graphs into dense and sparse parts.

We present a new scaling algorithm for maximum (or minimum) weight perfect
matching on general, edge weighted graphs. Our algorithm runs in
$O(m\sqrt{n}\log(nN))$ time, $O(m\sqrt{n})$ per scale, which matches the
running time of the best cardinality matching algorithms on sparse graphs. Here
$m,n,$ and $N$ bound the number of edges, vertices, and magnitude of any edge
weight. Our result improves on a 25year old algorithm of Gabow and Tarjan,
which runs in $O(m\sqrt{n\log n\alpha(m,n)} \log(nN))$ time.

We study a family of closelyrelated distributed graph problems, which we
call degree splitting, where roughly speaking the objective is to partition (or
orient) the edges such that each node's degree is split almost uniformly. Our
findings lead to answers for a number of problems, a sampling of which
includes:
 We present a $poly(\log n)$ round deterministic algorithm for
$(2\Delta1)\cdot (1+o(1))$edgecoloring, where $\Delta$ denotes the maximum
degree. Modulo the $1+o(1)$ factor, this settles one of the longstanding open
problems of the area from the 1990's (see e.g. Panconesi and Srinivasan
[PODC'92]). Indeed, a weaker requirement of $(2\Delta1)\cdot poly(\log
\Delta)$edgecoloring in $poly(\log n)$ rounds was asked for in the 4th open
question in the Distributed Graph Coloring book by Barenboim and Elkin.
 We show that sinkless orientationi.e., orienting edges such that each
node has at least one outgoing edgeon $\Delta$regular graphs can be solved
in $O(\log_{\Delta} \log n)$ rounds randomized and in $O(\log_{\Delta} n)$
rounds deterministically. These prove the corresponding lower bounds by Brandt
et al. [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight.
Moreover, these show that sinkless orientation exhibits an exponential
separation between its randomized and deterministic complexities, akin to the
results of Chang et al. for $\Delta$coloring $\Delta$regular trees.
 We present a randomized $O(\log^4 n)$ round algorithm for orienting
$a$arboricity graphs with maximum outdegree $a(1+\epsilon)$. This can be also
turned into a decomposition into $a (1+\epsilon)$ forests when $a=\Omega(\log
n)$ and into $a (1+\epsilon)$ pseduoforests when $a=o(\log n)$. Obtaining an
efficient distributed decomposition into less than $2a$ forests was stated as
the 10th open problem in the book by Barenboim and Elkin.

We study the problem of computing the minimum cut in a weighted distributed
messagepassing networks (the CONGEST model). Let $\lambda$ be the minimum cut,
$n$ be the number of nodes in the network, and $D$ be the network diameter. Our
algorithm can compute $\lambda$ exactly in $O((\sqrt{n} \log^{*} n+D)\lambda^4
\log^2 n)$ time. To the best of our knowledge, this is the first paper that
explicitly studies computing the exact minimum cut in the distributed setting.
Previously, nontrivial sublinear time algorithms for this problem are known
only for unweighted graphs when $\lambda\leq 3$ due to Pritchard and
Thurimella's $O(D)$time and $O(D+n^{1/2}\log^* n)$time algorithms for
computing $2$edgeconnected and $3$edgeconnected components.
By using the edge sampling technique of Karger's, we can convert this
algorithm into a $(1+\epsilon)$approximation $O((\sqrt{n}\log^{*}
n+D)\epsilon^{5}\log^3 n)$time algorithm for any $\epsilon>0$. This improves
over the previous $(2+\epsilon)$approximation $O((\sqrt{n}\log^{*}
n+D)\epsilon^{5}\log^2 n\log\log n)$time algorithm and
$O(\epsilon^{1})$approximation $O(D+n^{\frac{1}{2}+\epsilon}
\mathrm{poly}\log n)$time algorithm of Ghaffari and Kuhn. Due to the lower
bound of $\Omega(D+n^{1/2}/\log n)$ by Das Sarma et al. which holds for any
approximation algorithm, this running time is tight up to a $ \mathrm{poly}\log
n$ factor.
To get the stated running time, we developed an approximation algorithm which
combines the ideas of Thorup's algorithm and Matula's contraction algorithm. It
saves an $\epsilon^{9}\log^{7} n$ factor as compared to applying Thorup's tree
packing theorem directly. Then, we combine Kutten and Peleg's tree partitioning
algorithm and Karger's dynamic programming to achieve an efficient distributed
algorithm that finds the minimum cut when we are given a spanning tree that
crosses the minimum cut exactly once.

In this paper, we study the problem of approximating the minimum cut in a
distributed messagepassing model, the CONGEST model. The minimum cut problem
has been wellstudied in the context of centralized algorithms. However, there
were no known nontrivial algorithms in the distributed model until the recent
work of Ghaffari and Kuhn. They gave algorithms for finding cuts of size
$O(\epsilon^{1}\lambda)$ and $(2+\epsilon)\lambda$ in
$O(D)+\tilde{O}(n^{1/2+\epsilon})$ rounds and $\tilde{O}(D+\sqrt{n})$ rounds
respectively, where $\lambda$ is the size of the minimum cut. This matches the
lower bound they provided up to a polylogarithmic factor. Yet, no scheme that
achieves $(1+\epsilon)$approximation ratio is known. We give a distributed
algorithm that finds a cut of size $(1+\epsilon)\lambda$ in
$\tilde{O}(D+\sqrt{n})$ time, which is optimal up to polylogarithmic factors.

The {\em maximum cardinality} and {\em maximum weight matching} problems can
be solved in time $\tilde{O}(m\sqrt{n})$, a bound that has resisted improvement
despite decades of research. (Here $m$ and $n$ are the number of edges and
vertices.) In this article we demonstrate that this "$m\sqrt{n}$ barrier" is
extremely fragile, in the following sense. For any $\epsilon>0$, we give an
algorithm that computes a $(1\epsilon)$approximate maximum weight matching in
$O(m\epsilon^{1}\log\epsilon^{1})$ time, that is, optimal {\em linear time}
for any fixed $\epsilon$. Our algorithm is dramatically simpler than the best
exact maximum weight matching algorithms on general graphs and should be
appealing in all applications that can tolerate a negligible relative error.
Our second contribution is a new {\em exact} maximum weight matching
algorithm for integerweighted bipartite graphs that runs in time
$O(m\sqrt{n}\log N)$. This improves on the $O(Nm\sqrt{n})$time and
$O(m\sqrt{n}\log(nN))$time algorithms known since the mid 1980s, for $1\ll
\log N \ll \log n$. Here $N$ is the maximum integer edge weight.