TITLE: Memory Requirement for Universal Routing Schemes AUTHORS: Pierre Fraigniaud and Cyril Gavoille ABSTRACT: In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In~\cite{PU89}, Peleg and Upfal showed that there is no hope to do that with less than a total $\Omega(n^{1+1/(2s+4)})$ memory bits for any stretch factor $s \geq 1$. We improve this bound for stretch factors $s < 2$ by proving that any near-shortest path routing scheme uses a total of $\Omega(n^2)$ memory bits.