Labeling schemes are a prevalent paradigm in various computing settings. In such schemes, an oracle is given an input graph and produces a label for each of its nodes, enabling the labels to be used for various tasks. In this talk, I will address the question of what happens in a labeling scheme if some labels are erased, e.g., due to communication loss with the oracle or hardware errors. I will present a new resilient labeling scheme which improves upon the state of the art in several computational aspects and I will show that it is nearly optimal.