A better way to summarize the central question of this paper would be: "Why is it that a large-parameter model trained with gradient descent on real data _could_ just memorize all of the training data (it has the capacity) yet finds solutions which generalize well to an unseen test set?"
To say that deep learning is _just_ memorizing its training data would be incorrect. We have empirical evidence to the contrary and this paper is part of that evidence.
Generalization is a multi-axis scale, not a switch: you can have more or less generalization in many different dimensions. Being terrible at adversarial examples just means that axis is weak.
>"Specifically, we take a candidate architecture and train it both on the true data and on a copy of the data in which the true labels were replaced by random labels. In the second case, there is no longer any relationship between the instances and the class labels. As a result, learning is impossible."
This is like saying learning someones phone number is impossible because there is no relationship between the person and the number.
Memorization is pretty easy. Generalizing from past examples requires that there be a relationship not just between one person and their phone number but between all people and their phone numbers.
What is there to understand? As far as I know the shapes we use for letters are arbitrary (at least at this point).