We are pleased to thank all reviewers for the relevant feedback.$ In response of Reviewer_1, we are grateful for the recommendation of the FOCS’14 guidelines; we were not aware of that document. We understand the importance of making the paper accessible to the widest audience from the very introduction, therefore we shall make structural changes to the presentation in this sense. High-level versions of Theorem 3 and Algorithm 1/2 will be drafted in the introduction. We also acknowledge the remark on the “main” novelty as indeed there are several equally important contributions, not limited to Theorem 3. In response to Reviewer_6, we agree in that the literature background of Section 5.1 and Theorem 10 could be expanded. The camera-ready version will refer to other known results on robustness. In addition, we would like to bring to Reviewer_6’s attention that real-world experiments on the proposed method are ongoing and should hopefully be made public soon. Although we believe that any finding in this direction would be out of the scope of the present work and it will be addressed in a future publication.