Neural networks are vulnerable to slight alterations to otherwise correctly classified inputs, leading to incorrect predictions. To rigorously assess the robustness of neural networks against such perturbations, verification techniques can be employed. Robustness is generally measured in terms of adversarial accuracy, based on an upper bound on the magnitude of perturbations commonly denoted by ε. For each input in a given set, a verifier determines whether a perturbation up to magnitude ε can deceive the network. In this work, we contribute novel analysis techniques for the verified robustness of neural networks for supervised classification problems and report on interesting findings we obtained using these techniques. We utilise the notion of robustness distributions, specifically those built using the concept of critical ε values. Critical ε values are defined as the maximum amount of perturbation for which a given input is provably correctly classified, such that any larger perturbations can cause misclassification. To effectively estimate the critical ε values for each input in a given set, we utilise a variant of the binary search algorithm. We then analyse the distributions of these critical ε values over a given set of inputs for 12 MNIST classifiers widely used in the literature on neural network verification. Using a Kolmogorov-Smirnov test, we obtain support for the hypothesis that the critical ε values of 11 of these networks follow a log-normal distribution. Furthermore, we found no statistically significant differences between the critical ε distributions for training and testing data for 12 feed-forward neural networks on the MNIST dataset. Generally, we find a strong positive correlation between the critical ε of an input image across various networks. However, in some cases, an input that is easily perturbed to deceive one network may require a considerably larger perturbation to deceive another. Furthermore, for a given input, the adversarial examples that we find differ across networks, with different predicted classes associated with them. We investigate the effect adversarial training can have on the critical ε distribution of various neural networks for MNIST, CIFAR and GTSRB datasets. We also find that complete verification is expensive for some of the CIFAR and GTSRB networks, which limits the precision of the robustness distributions we were able to obtain. Nonetheless, we observe that most of the critical ε distributions of the networks obtained through adversarial training do not follow a log-normal distribution. Furthermore, adversarial training significantly improves the critical ε distributions for testing as well as training data in most cases. Lastly, we provide a ready-to-use Python package available on GitHub that can be used for creating robustness distributions and enables others to build upon our work.

The min-diameter of a directed graph $G$ is a measure of the largest distance between nodes. It is equal to the maximum min-distance $d_{min}(u,v)$ across all pairs $u,v \in V(G)$, where $d_{min}(u,v) = \min(d(u,v), d(v,u))$. Our work provides a $O(m^{1.426}n^{0.288})$-time $3/2$-approximation algorithm for min-diameter in DAGs, and a faster $O(m^{0.713}n)$-time almost-$3/2$-approximation variant. (An almost-$α$-approximation algorithm determines the min-diameter to within a multiplicative factor of $α$ plus constant additive error.) By a conditional lower bound result of [Abboud et al, SODA 2016], a better than $3/2$-approximation can't be achieved in truly subquadratic time under the Strong Exponential Time Hypothesis (SETH), so our result is conditionally tight. We additionally obtain a new conditional lower bound for min-diameter approximation in general directed graphs, showing that under SETH, one cannot achieve an approximation factor below 2 in truly subquadratic time. We also present the first study of approximating bichromatic min-diameter, which is the maximum min-distance between oppositely colored vertices in a 2-colored graph.

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of $w$ workers and a multiset $T \subseteq[t]$ of $|T|=w$ tasks, a memoryless worker-task assignment function is any function $ϕ$ that assigns the workers $[w]$ to the tasks $T$ based only on the current value of $T$. The assignment function $ϕ$ is said to have switching cost at most $k$ if, for every task multiset $T$, changing the contents of $T$ by one task changes $ϕ(T)$ by at most $k$ worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost $O(\log w \log (wt))$ and an explicit construction that achieves switching cost $\operatorname{polylog} (wt)$. We also prove a super-constant lower bound on switching cost: we show that for any value of $w$, there exists a value of $t$ for which the optimal switching cost is $w$. Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of $w$. Finally, we present an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.