  A partition $(C_1,C_2,...,C_q)$ of $G = (V,E)$ into clusters of strong
(respectively, weak) diameter $d$, such that the supergraph obtained by
contracting each $C_i$ is $\ell$-colorable is called a strong (resp., weak)
$(d, \ell)$-network-decomposition. Network-decompositions were introduced in a
seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al.
showed that strong $(exp\{O(\sqrt{ \log n \log \log n})\}, exp\{O(\sqrt{ \log n
\log \log n})\})$-network-decompositions can be computed in distributed
deterministic time $exp\{O(\sqrt{ \log n \log \log n})\}$.
  The result of Awerbuch et al. was improved by Panconesi and Srinivasan in
1992: in the latter result $d = \ell = exp\{O(\sqrt{\log n})\}$, and the
running time is $exp\{O(\sqrt{\log n})\}$ as well. Much more recently Barenboim
(2012) devised a distributed randomized constant-time algorithm for computing
strong network decompositions with $d = O(1)$. However, the parameter $\ell$ in
his result is $O(n^{1/2 + \epsilon})$.
  In this paper we drastically improve the result of Barenboim and devise a
distributed randomized constant-time algorithm for computing strong $(O(1),
O(n^{\epsilon}))$-network-decompositions. As a corollary we derive a
constant-time randomized $O(n^{\epsilon})$-approximation algorithm for the
distributed minimum coloring problem, improving the previously best-known
$O(n^{1/2 + \epsilon})$ approximation guarantee. We also derive other improved
distributed algorithms for a variety of problems.
  Most notably, for the extremely well-studied distributed minimum dominating
set problem currently there is no known deterministic polylogarithmic-time
algorithm. We devise a {deterministic} polylogarithmic-time approximation
algorithm for this problem, addressing an open problem of Lenzen and
Wattenhofer (2010).
