Embeddings and labeling schemes for A*
  A* is a classic and popular method for graphs search and path finding. It
assumes the existence of a heuristic function $h(u,t)$ that estimates the
shortest distance from any input node $u$ to the destination $t$.
Traditionally, heuristics have been handcrafted by domain experts. However,
over the last few years, there has been a growing interest in learning
heuristic functions. Such learned heuristics estimate the distance between
given nodes based on "features" of those nodes.
  In this paper we formalize and initiate the study of such feature-based
heuristics. In particular, we consider heuristics induced by norm embeddings
and distance labeling schemes, and provide lower bounds for the tradeoffs
between the number of dimensions or bits used to represent each graph node, and
the running time of the A* algorithm. We also show that, under natural
assumptions, our lower bounds are almost optimal.
