We would like to thank the reviewers for their comments and suggestions. We limit ourselves to a few brief remarks, since we agree with most of the reviewers comments.$
Assigned_Reviewer_1:  We agree that our primary contribution is theoretical. However, the empirical performance is better than backpropagation. Also using the recursive kernel with k=4 improves over k=1, which makes our algorithm different from typical kernel svm that generally uses a polynomial or RBF kernel. 

Assigned_Reviewer_2: The reviewer is absolutely correct that we should have cited Cho and Saul, which is a very relevant paper. We will fix this in the revision. We will also cite Andoni et al. and Hazan and Jaakola which are also related. 

Assigned_Reviewer_3: When L is sqrt(log(d)) and k=1, then our algorithm is polynomial time. However when L=log(d) and k>1, then our algorithm is exponential time. The reviewer is correct in pointing out that the lower bound is polynomial time in either case. We will add this discussion to the revision. Thank you for pointing this out, as this is a place that might lead to interesting new results.