  In this paper, we study the problem of computing an edge-coloring in the
(one-pass) W-streaming model. In this setting, the edges of an $n$-node graph
arrive in an arbitrary order to a machine with a relatively small space, and
the goal is to design an algorithm that outputs, as a stream, a proper coloring
of the edges using the fewest possible number of colors.
  Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial
algorithm for this problem, which computes in $\tilde{O}(n)$ space a proper
$O(\Delta^2)$-coloring w.h.p. (here $\Delta$ is the maximum degree of the
graph). Subsequent papers improved upon this result, where latest of them
[Ansari et al., 2022] shows that it is possible to deterministically compute an
$O(\Delta^2/s)$-coloring in $O(ns)$ space. However, none of the improvements,
succeeded in reducing the number of colors to $O(\Delta^{2-\epsilon})$ while
keeping the same space bound of $\tilde{O}(n)$. In particular, no progress was
made on the question of whether computing an $O(\Delta)$-coloring is possible
with roughly $O(n)$ space, which was stated in [Behnezhad et al., 2019] to be a
major open problem.
  In this paper we bypass the quadratic bound by presenting a new randomized
$\tilde{O}(n)$-space algorithm that uses $\tilde{O}(\Delta^{1.5})$ colors.
