  We consider the classical Minimum Crossing Number problem: given an
$n$-vertex graph $G$, compute a drawing of $G$ in the plane, while minimizing
the number of crossings between the images of its edges. This is a fundamental
and extensively studied problem, whose approximability status is widely open.
In all currently known approximation algorithms, the approximation factor
depends polynomially on $\Delta$ -- the maximum vertex degree in $G$. The best
current approximation algorithm achieves an $O(n^{1/2-\varepsilon}\cdot
\text{poly}(\Delta\cdot\log n))$-approximation, for a small fixed constant
$\epsilon$, while the best negative result is APX-hardness, leaving a large gap
in our understanding of this basic problem. In this paper we design a
randomized $O\left(2^{O((\log n)^{7/8}\log\log
n)}\cdot\text{poly}(\Delta)\right )$-approximation algorithm for Minimum
Crossing Number. This is the first approximation algorithm for the problem that
achieves a subpolynomial in $n$ approximation factor (albeit only in graphs
whose maximum vertex degree is subpolynomial in $n$).
  In order to achieve this approximation factor, we design a new algorithm for
a closely related problem called Crossing Number with Rotation System, in
which, for every vertex $v\in V(G)$, the circular ordering, in which the images
of the edges incident to $v$ must enter the image of $v$ in the drawing is
fixed as part of the input. Combining this result with the recent reduction of
[Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation
algorithm for Minimum Crossing Number. We introduce several new technical
tools, that we hope will be helpful in obtaining better algorithms for the
problem in the future.
