A great deal of recent work has proposed methods for "provable" or "certified" adversarial defenses: methods that guarantee that a
classifier will not change its prediction given small perturbations to the input. However, one major line of work in this area, based upon linear programming relaxations and duality (or equivalently, propagating uncertainly bounds through the network), has seemingly reached a plateau in performance, unable to train/verify networks at larger scales. In this talk, I will assess some of the reasons why this limit has been reached, and then highlight a simple alternative approach that does scale to much larger classifiers: randomized smoothing. I will present a simple overview of randomized smoothing techniques for adversarial robustness, and how they can (somewhat counterintuitively) lead to worst-case bounds rather than just average-case bounds. I will conclude with a discussion of the limitations of randomized smoothing, and whether there exists any possibility to combine these two paradigms in adversarial robustness.