Computational Limitations in Robust Classification and Win-Win Results

Akshay Degwekar, Preetum Nakkiran, Vinod Vaikuntanathan

We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of…