This paper provides theory that explains what functions can be learned using RNNs (beyond linear classifiers) and gives sample complexity bounds. All reviewers agree that this result is significant and therefore, I recommend acceptance.