Understanding the inductive bias of neural networks is critical to explaining their ability to generalise. Here, for one of the simplest neural networks -a single-layer perceptron with n input neurons, one output neuron, and no threshold bias termwe prove that upon random initialisation of weights, the a priori probability P (t) that it represents a Boolean function that classifies t points in {0, 1}
n as 1 has a remarkably simple form: P (t) = 2 −n for 0 ≤ t < 2 n . Since a perceptron can express far fewer Boolean functions with small or large values of t (low "entropy") than with intermediate values of t (high "entropy") there is, on average, a strong intrinsic a-priori bias towards individual functions with low entropy. Furthermore, within a class of functions with fixed t, we often observe a further intrinsic bias towards functions of lower complexity. Finally, we prove that, regardless of the distribution of inputs, the bias towards low entropy becomes monotonically stronger upon adding ReLU layers, and empirically show that increasing the variance of the bias term has a similar effect.
The topic of the paper is the inductive bias of neural networks. The authors study a simple model, namely a perceptron with no bias term viewed as a mapping from {0,1}^n->{0,1}. They show that initializing weights with a distribution that is symmetric under coordinate sign flips corresponds to an initialization in function space that is biased towards low-entropy functions. They also exhibit empirical evidence that by adding a bias term, or by using multiple layers, this tendency towards low entropy appears to increase. They also prove a bound on the minimal size of a network in order for it to represent all boolean functions. Finally, they prove a result that suggests that for ReLU networks with infinite widths the bias towards low-entropy function does indeed increase with depth. 
My main concern regarding this paper is that the claim in the title and the statement of Theorem 4.1 seem to rely crucially on the fact that the functions are viewed with input as {0,1}^n. The origin of the "simplicity", in the basic case that the authors address (perceptrons with no bias) appears to be a consequence that hyperplanes through the origin are quite likely to classify input points in {0,1}^n similarly. If one switches to a symmetric domain, for example {-1,1}, the effect in this setting completely disappears. The authors actually mention this in Section 5, noting that the expressivity of the perceptron is much lower for centered inputs. However, this to me suggests that Theorem 4.1 is not capturing any significant aspect of neural networks (in fact, the statement is a property of how linear hyperplanes to separate {0,1}^n, not neural networks). I may be mistaken, but I would like the authors to clarify this point.
Another concern is related to Theorem 5.5. This might be a more substantial result, but it is difficult to interpret and its implications are not discussed. Understanding the effect of depth on the "simplicity bias" seems to me an important problem, but for some reason Theorem 5.5 (which deals with deep neural networks rather than linear perceptrons) is emphasized much less than Theorem 4.1. Why is this the case?
The paper is well-written but not always very clear. In particular, notation is not always defined and the authors use on notions from complexity theory that are not introduced (e.g., Lepel-Ziv complexity).
Other comments: 
* Is the set F_t is defined as set of all functions with assigned \mathcal T, but later this seems to be restricted to the functions expressible by a network/perceptron.
* Definition 3.5: this defined the entropy H(f) of a function but then write H(p). It should probably be H(f) = -plog p - (1-p)log(1-p) where p = \mathcal T(f), right?
* Definition 3.6: some context or references for this definition could be useful.
* Regarding the fact that functions in F_t are not uniform, shouldn't the distribution be the same for isotropic weight distributions? Assuming the distribution of w/|w| is uniform on the sphere, a more precise description of  P(f) seems possible
* Section 4.3: what is the "rank" in this setting? Isn't the parameter a vector w in R^n?
* Some typos: Definition 3.1 w_l \in R^{n_{l+1}}, ",." in the beginning of Section 5, several in the last paragraph of Section 5.