The random part is fundamental to the result working, and makes things easier and not harder (i.e. structured nets are outliers from the point of view of this result). Assuming structure makes things hard. Saying something nontrivial for too general settings tends to run into cryptography results around hashes—though I think ARC is interested in extensions with controlled structure. In particular I think they know that if the structure comes from Bayesian-learning training on a small set of datapoints then a version of their result extends to that setting
The random part is fundamental to the result working, and makes things easier and not harder (i.e. structured nets are outliers from the point of view of this result). Assuming structure makes things hard. Saying something nontrivial for too general settings tends to run into cryptography results around hashes—though I think ARC is interested in extensions with controlled structure. In particular I think they know that if the structure comes from Bayesian-learning training on a small set of datapoints then a version of their result extends to that setting