Reviews: Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes

The main contribution of this work is a new approach to neural network robustness based on polyhedral complexes. Quality: The theoretical results are clear and intuition explained. The proposed algorithms are clever and neatly explained. The main missing component is more extensive empirical evaluation: -- 128 random samples seems very small to draw reliable conclusions -- Only one type of network is considered (binary classification 1 vs. 7 on MNIST via standard training): The performance of a verifier typically varies a lot depending on how the network was trained (whether it was trained to be robust and by which method). For example, training to enforce relu stability would reduce the iteration time as mentioned in the paper. How does this compare to other LP/SDP based incomplete verifiers?