Computational Asymmetries in Robust Classification

Samuele Marro, Michele Lombardi

In the context of adversarial robustness, we make three strongly related contributions. First, we prove that while attacking ReLU classifiers is $NP$-hard, ensuring their…