TITLE: A Space Lower Bound for Routing in Trees AUTHORS: Pierre Fraigniaud and Cyril Gavoille ABSTRACT: The design of compact routing schemes in trees form the kernel of sophisticated strategies for compact routing in arbitrary graphs. This paper focuses on the space complexity for routing messages along shortest paths in trees. It was recently shown that the family of n-node trees supports routing schemes using addresses and routing tables of size O(log2n/loglogn) bits per node, if the output port numbers of each node are chosen by an adversary. This paper shows that this result is tight, that is the sum of the sizes of the address and of the local routing table is at least Omega(log2n/loglogn) bits for some node of some tree.